1.实验目的
(1)掌握动态规划法的处理思路与算法框架。
(2)掌握应用动态规划法解决具体问题的方法。
(3)掌握动态规划法的广泛应用。
2.实验内容
(1)问题描述
(2)输入
(3)输出
输出分为两行。
第一行输出一个整数，表示矩阵在以最优计算次序求解连乘积时，所需要计算的次数。
第二行输出求解矩阵连乘积的最优次序。
3.问题实例分析
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 |
| 0 | 1500 | |||
| 0 | 750 | |||
| 0 | 750 | |||
| 0 | 1500 | |||
| 0 |
| 0 | 1500 | 1750 | ||
| 0 | 750 | 1000 | ||
| 0 | 750 | 3000 | ||
| 0 | 1500 | |||
| 0 |
| 0 | 1500 | 1750 | 1500 | |
| 0 | 750 | 1000 | 1750 | |
| 0 | 750 | 3000 | ||
| 0 | 1500 | |||
| 0 |
| 0 | 1500 | 1750 | 1500 | 4500 |
| 0 | 750 | 1000 | 1750 | |
| 0 | 750 | 3000 | ||
| 0 | 1500 | |||
| 0 |
| 0 | 1 | 1 | 1 | 4 |
| 0 | 2 | 3 | 4 | |
| 0 | 3 | 4 | ||
| 0 | 4 | |||
| 0 |
4.算法描述及说明
正如第3节问题实例分析所述，算法的整体流程如下：
5.算法正确性分析
7.运行结果展示及其说明
测试样例使用了两组。对于每一组测试样例，都正确地输出了计算次数与次序，并在最后给出了最优的加括号的方案。
8.心得体会
9.程序源代码
#include<iostream> const int N = 1005; long long dp[N][N]; long long p[N]; int pos[N][N]; int posl[N];//记录左括号位置 int posr[N];//记录右括号位置 using namespace std; void traceback(int i,int j) { if (i == j) return; traceback(i, pos[i][j]); traceback(pos[i][j] + 1, j); posl[i]++; posr[j]++; cout << "Multiply A" << i << "," << pos[i][j] << " and A" << pos[i][j] + 1 << "," << j<<endl; } int main() { int n; cin >> n; for (int i = 0; i <= n; i++) cin >> p[i]; for (int i = 1; i <= n; i++) dp[i][i] = 0; for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; dp[i][j] = dp[i + 1][j] + p[i - 1] * p[i] * p[j]; pos[i][j] = i; for (int k = i + 1; k < j; k++) { int t = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]; if (t < dp[i][j]) { dp[i][j] = t; pos[i][j] = k; } } } } cout << "计算次数" << dp[1][n] << endl; traceback(1, n); for (int i = 1; i <= n; i++) { for (int j = 0; j < posl[i]; j++) cout << '('; cout << 'A' << i ; for (int j = 0; j < posr[i]; j++) cout << ')'; } }
