python-矩阵乘法

解题思路：

1896-矩阵乘法，代码超限了，记录以下自己学到的思路吧

动态规划

①建立一个dp数组其中dp[i][j]表示第i个矩阵到第j个矩阵的最小乘法次数

②初始化dp[i][i] = 0(i = 1 to n)

③状态转移方程

dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+A[i]*A[k+1]*A[j+1])

参考代码：

from cmath import inf  
  
  
def f(n):  
    A = [0]+[int(i) for i in input().strip().split()]  
    dp = [[inf for j in range(n+1)] for i in range(n+1)]  
  
    for i in range(1,n+1):  
        dp[i][i] = 0  
      
    for  t in range(1,n):        #t是每次在i的基础上加的值
        for i in range(1,n-t+1): #依次把相隔为[1 to n-1]的矩阵的最少乘法更新一遍，目的是在状态转换方程中引入第k个矩阵时使用
            j = i+t              
            for k in range(i,j):  
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+A[i]*A[k+1]*A[j+1])  
    print(dp[1][n])  
  
if __name__ == '__main__':  
   n = int(input().strip())  
   f(n)