矩阵连乘问题
题目信息
输入
共两行
第一行 N (1<=N<=100)，代表矩阵个数。
第二行有N+1 个数，分别为 q(0), q(1), ..., q(n) (1<=q(k)<=2000), 代表第 k 个矩阵是q(k-1)xq(k)维的。
输出
共两行
第一行 M，为最优代价。注：测试用例中 M 值保证小于 2^31
第二行为最优顺序。如 (A1((A2A3)A4)) ，最外层也加括号。
注意:测试用例已经保证了输出结果唯一,所以没有AAA的情况.
测试样例
样例1
6
30 35 15 5 10 20 25
15125
((A1(A2A3))((A4A5)A6))
样例2
1
1 1
0
(A1)
解答
方法一·普通动规
#include <iostream>
#include <climits>
using namespace std;
#define MAX 2010
int ans[MAX][MAX] = {0};//保存矩阵链 A[i..j]的最小代价
int divide[MAX][MAX] = {0};//记录最小代价ans[i,j]对应的分割点
/* 计算n元矩阵链p的最优代价
* 动态规划的每一步结果储存在 ans与 divide中 */
void MatrixChainOrder(int p[], int n)
{
//矩阵链长度为2到n
for (int l = 2; l <= n; l++)
{ //讨论长度为l的矩阵链A[i..j]
for (int i = 1; i <= n - l + 1; i++)
{
int j = i + l - 1;
ans[i][j] = INT_MAX;
//依次讨论每一个分割点d:将矩阵链A[i..j]分成A[i..d]和 A[d+1..j]
for (int temp, d = i; d < j; d++)
{
temp = ans[i][d] + ans[d + 1][j] + p[i - 1] * p[d] * p[j];
//记录下矩阵链A[i..j]最小的情况
if (temp < ans[i][j])
{
ans[i][j] = temp;
divide[i][j] = d;
}
}
}
}
}
//根据divide数组，输出A[i..j]的最优情况
void PrintDivide(int i, int j)
{
if (i == j)
{
cout << "A" << i;
}
else
{
int d = divide[i][j];//分界点
cout << "(";
PrintDivide(i, d);//左
PrintDivide(d + 1, j);//右
cout << ")";
}
}
int main()
{
freopen("E://test.txt", "r", stdin);
freopen("E://out.txt", "w", stdout);
int n;
cin >> n;
int p[MAX];
for (int temp, i = 0; i <= n; i++)
cin >> p[i];
MatrixChainOrder(p, n);
cout << ans[1][n] << endl;
if (n == 1)
{
cout << "(A1)";
}
else
{
PrintDivide(1, n);
}
cout << endl;
return 0;
}
方法二·优化的动规
#include <iostream>
#include <climits>
using namespace std;
#define MAX 2010
int ans[MAX][MAX] = {0}; // 保存矩阵链 A[i..j]的最小代价
int divide[MAX][MAX] = {0}; // 记录最小代价ans[i,j]对应的分割点
/* 计算n元矩阵链p的最优代价
* 动态规划的每一步结果储存在 ans与 divide中 */
void MatrixChainOrder(int p[], int n)
{
//初始化divide数组
for (int i = 1; i <= n; i++)
{
divide[i][i] = i;
}
//矩阵链长度为2到n
for (int l = 2; l <= n; l++)
{
//讨论长度为l的矩阵链A[i..j]
for (int i = 1; i <= n - l + 1; i++)
{
int j = i + l - 1;
ans[i][j] = INT_MAX;
//在特定区间内：依次讨论每一个分割点d，将矩阵链A[i..j]分成A[i..d]和 A[d+1..j]
for (int temp, d = divide[i][j - 1]; d <= divide[i + 1][j]; d++)
{
temp = ans[i][d] + ans[d + 1][j] + p[i - 1] * p[d] * p[j];
//记录下矩阵链A[i..j]最小的情况
if (temp < ans[i][j])
{
ans[i][j] = temp;
divide[i][j] = d;
}
}
}
}
}
/* 根据divide数组，输出A[i..j]的最优情况 */
void PrintDivide(int i, int j)
{
if (i == j)
{
cout << "A" << i;
}
else
{
int d = divide[i][j];//分界点
cout << "(";
PrintDivide(i, d);//左
PrintDivide(d + 1, j);//右
cout << ")";
}
}
int main()
{
freopen("E://test.txt", "r", stdin);
freopen("E://out.txt", "w", stdout);
int n;
cin >> n;
int p[MAX];
for (int temp, i = 0; i <= n; i++)
cin >> p[i];
MatrixChainOrder(p, n);
cout << ans[1][n] << endl;
if (n == 1)
{
cout << "(A1)";
}
else
{
PrintDivide(1, n);
}
cout << endl;
return 0;
}
想法
还有老师介绍的另一种方法，自顶而下的一种方法，更加适合于只用计算部分即可的题
1. 对所有i,j, m[i,j]=0
2. LU(1,n) //LookUp
LU(i,j)
1. 若 m[i,j]>0, 返回 m[i,j]
2. 若 i = = j, 返回0
3. s[i,j] = i; m[i,j] = LU(i,i) + LU(i+1,j) + qi-1qiqj;
4. 对 k = i + 1 到 j-1
5. t = LU(i, k) + LU(k+1,j) + qi-1qkqj,
6. 若m[i,j]>t, 则m[i,j]=t; s[i,j]=k;
7. 返回m[i][j]
自底向上与自顶向下的比较
动态规划方法采用自底向上
备忘录方法采用自顶向下
都能解决重叠子问题
当所有子问题都至少要求解一次时,用动态规划方法比较好
当部分子子问题不用求解时,用备忘录方法比较好
矩阵连乘问题宜用动态规划