题目分析

题目给出了矩阵的个数n，并紧接着给出n行矩阵的行和列，最后给出一个矩阵相乘的顺序，其中A、B、C等等分别直接对应每一个按顺序输入的矩阵

最终题目要求输出按照既定顺序规定的运算次数

方法一：栈思路处理

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)$ ，遍历所有矩阵或规定计算顺序的字符串的代价，其中N为矩阵的数量
空间复杂度： $O (N)$ ，存储矩阵数据的空间大小，和其他一些等代价的空间申请的大小

方法二：递归

实现思路
- 我们发现表示计算顺序的输入字符串是严格遵守括号匹配的要求的
- 因此每一对括号内的计算过程就可以类比成一个子问题，因此递归的情景就可以确定下来
- 递归函数recurse(s, arr)表示当前要分析的子字符串为s，借助的是一开始录入的arr矩阵信息将A,B,C等矩阵定位成第几个输入的矩阵信息，其返回的结果表示 $[计算得到的新的矩阵的行，计算得到的新的矩阵的列， 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 (N^{2})$ ，每次层递归遍历平均s的长度会去掉一个矩阵符号(A-Z)和一对括号的长度，相当于遍历的代价为 $O (N) = ((N) + (N - 3) + (N - 6) . . . + 2) = O (N^{2})$ ，其中N为矩阵的数量
空间复杂度： $O (N)$ ，存储矩阵数据的空间大小，和其他一些等代价的空间申请的大小

题解 | #矩阵乘法计算量估算#

题目分析

方法一：栈思路处理

复杂度分析

方法二：递归

复杂度分析