矩阵相乘加括号（矩阵连乘问题，采用动态规划）
leetcode题库中暂时没有该题目。
1. 题目描述
2. 思路
2.1 动态规划的 状态矩阵 和 边界
把状态矩阵及其边界想清楚了，到这里先不往下看，可以自己想想递推方程，然后写代码试试。
2.2 状态矩阵的递推方程
3 代码
Python
def func(p):
n = len(p)-1
results = [[0 for j in range(len(p))] for i in range(len(p))]
for k in range(2, n+1):
for i in range(n-k+1):
results[i][i+k] = min([ p[i]*p[i+j] *p[i+k] + results[i][i+j]+results[i+j][i+k] for j in range(1,k)])
#print(results)
return results[0][n]
p1=[10,100,5,50] # 正确答案是7500
p2 = [30,35,15,5,10,20] # 正确答案是11875
print(func(p1))
print(func(p2))
评论 (1)
