题目分析

  1. 题目给出了矩阵的个数n,并紧接着给出n行矩阵的行和列,最后给出一个矩阵相乘的顺序,其中A、B、C等等分别直接对应每一个按顺序输入的矩阵
  2. 最终题目要求输出按照既定顺序规定的运算次数

方法一:栈思路处理

alt

  • 实现思路
    • 我们发现在规定的矩阵相乘的顺序中,是由括号所规定的
    • 每次我们读到一个新的矩阵时(标记为A-Z),我们将其放入栈中(维护一个列表)
    • 当读到右括号的时候,说明当前栈顶的两个矩阵需要进行运算,我们此时统计并累计本次运算的次数
    • 然后将上一步计算后的新矩阵重新入栈
    • 直到所有的右括号都被读完,说明所有步骤也计算完成
    • 返回最终的计算次数结果
while True:
    try:
        n = int(input())
        arr = []
        order = []
        res = 0
        for i in range(n):
            arr.append(list(map(int, input().split())))    # 处理输入的矩阵行列数据
        f = input()
        for i in f:
            if i.isalpha():
                order.append(arr[ord(i)-65])               # 将字母转换成第几个矩阵的处理信息
            elif i == ')' and len(order) >= 2:             # 读到右括号就处理最近的两个矩阵相乘的结果
                b = order.pop()
                a = order.pop()
                res += a[1]*b[1]*a[0]                      # 累计到res中
                order.append([a[0], b[1]])
        print(res)
    except:
        break

复杂度分析

  • 时间复杂度:O(N)O(N),遍历所有矩阵或规定计算顺序的字符串的代价,其中N为矩阵的数量
  • 空间复杂度:O(N)O(N),存储矩阵数据的空间大小,和其他一些等代价的空间申请的大小

方法二:递归

  • 实现思路
    • 我们发现表示计算顺序的输入字符串是严格遵守括号匹配的要求的
    • 因此每一对括号内的计算过程就可以类比成一个子问题,因此递归的情景就可以确定下来
    • 递归函数recurse(s, arr)表示当前要分析的子字符串为s,借助的是一开始录入的arr矩阵信息将A,B,C等矩阵定位成第几个输入的矩阵信息,其返回的结果表示[s][计算得到的新的矩阵的行,计算得到的新的矩阵的列,s内的计算次数]
    • 递归函数内部要处理的工作为
      • 遍历整个字符串s

      • 如果访问到s内部有括号部分,则分析出s内部的新的一对括号,找到这一对括号后进行新的的递归调用,返回一个新的矩阵和内部计算的次数结果,将此信息存储在a或b中

      • 如果访问到s内部无括号部分,则利用arr将A,B,C等矩阵定位到第几个输入矩阵,并存储在b或a中

      • 因此s中一定是可以通过递归提炼成两个矩阵进行计算的操作,对a和b进行矩阵运算,并将新的结果矩阵+累计的计算次数信息返回


def recurse(s, arr):
    st = []
    i = 0
    while i < len(s):                                        # 遍历待分析字符串
        if s[i] == '(':                                      # 从碰到第一个字符串内的左括号开始标记
            j = i+1
            level = 1
            while j < len(s):
                if s[j] == '(':
                    level += 1
                elif s[j] == ')':
                    level -= 1
                    if level == 0:                           # 一直到找到上面的左括号对应的封闭右括号为止
                        st.append(recurse(s[i+1:j], arr))    # 递归子字符串,按照括号划分的区域继续往内部递归
                        break
                j += 1
            i = j
        elif s[i].isalpha():                                 # 在遍历当前字符串时 如果遇到了A.B.C等矩阵符号,则相应加入st中
            x = ord(s[i]) - 65
            st.append(arr[x])
        i += 1
    b = st.pop()                                             # 此时st中有待计算的两个矩阵信息
    a = st.pop()    
    res = [a[0], b[1], a[2]+b[2]+a[0]*a[1]*b[1]]             # 计算出新矩阵的长和宽,并将计算的次数放到第三个位置中,等待上层递归回头累计
    return res

while True:
    try:
        n = int(input())
        arr = []
        order = []
        for i in range(n):
            l = input().split()
            l.append('0')
            arr.append(list(map(int, l)))    # 处理输入的矩阵长宽数据
        s = input()
        print(recurse(s[1:-1], arr)[2])      # 调用递归函数
    except:
        break
            

复杂度分析

  • 时间复杂度:O(N2)O(N^2),每次层递归遍历平均s的长度会去掉一个矩阵符号(A-Z)和一对括号的长度,相当于遍历的代价为O(N)=((N)+(N3)+(N6)...+2)=O(N2)O(N)=((N)+(N-3)+(N-6)...+2) = O(N^2) ,其中N为矩阵的数量
  • 空间复杂度:O(N)O(N),存储矩阵数据的空间大小,和其他一些等代价的空间申请的大小