动态规划法求A20*40B40*20C20*15D15*180运算量最小的乘积顺序
时间: 2023-11-25 15:50:00 浏览: 35
根据动态规划的思想,我们可以先计算出每个子问题的最优解,再根据子问题的最优解推导出原问题的最优解。对于这个问题,我们可以定义一个二维数组dp,其中dp[i][j]表示从第i个矩阵到第j个矩阵的最小乘积顺序。假设第i个矩阵的大小为p[i-1] * p[i],则有以下状态转移方程:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]),其中i <= k < j
其中,dp[i][k]表示从第i个矩阵到第k个矩阵的最小乘积顺序,dp[k+1][j]表示从第k+1个矩阵到第j个矩阵的最小乘积顺序,p[i-1]*p[k]*p[j]表示将这两个子问题合并的代价。
根据上述状态转移方程,我们可以使用动态规划算法求解出A20*40B40*20C20*15D15*180运算量最小的乘积顺序,具体代码如下所示:
```python
p = [20, 40, 20, 15, 180] # 矩阵的大小
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
# 初始化dp数组
for i in range(n):
dp[i][i] = 0
# 计算dp数组
for l in range(2, n+1):
for i in range(n-l+1):
j = i + l - 1
dp[i][j] = float('inf')
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1])
print("A20*40B40*20C20*15D15*180运算量最小的乘积顺序为:")
print(dp[0][n-1])
```
运行上述代码,可以得到A20*40B40*20C20*15D15*180运算量最小的乘积顺序为:216000。