【动态规划】区间DP - 最优矩阵链乘（另附POJ1651Multiplication Puzzle）

最优矩阵链乘（动态规划）

一个$n\ast m$的矩阵由 $n$ 行 $m$ 列共 $n\ast m$ 排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个nm的矩阵乘mp的矩阵，运算量为nmp。

矩阵乘法不满足分配律，但满足结合律。因此$A\ast B\ast C$既可以按顺序 $（A\ast B）\ast C$ 也可以按 $A\ast （B\ast C）$ 来进行。假设$A、B、C$ 分别是 $2\ast 3、3\ast 4、4\ast 5$ 的，则 $（A\ast B）\ast C$ 运算量是$2\ast 3\ast 4+2\ast 4\ast 5=64$，$A\ast （B\ast C）$的运算量是 $3\ast 4\ast 5\ast 2\ast 3\ast 5=90$ .显然第一种顺序节省运算量。

给出n个矩阵组成的序列，设计一种方法把他们依次乘起来，使得总的运算量尽量小。假设第i个矩阵A[i]是$P[i-1]\ast P[i]$的（意味着这些矩阵可以按顺序链乘，所以只需要考虑区间相乘中区间的选取）。

输入

3 2 3 4 5

输出

64

实际上就是区间DP的模板。 我们用$f(i,j)$表示A[i]、A[i+1]...A[j]乘起来的最少运算数

状态转移方程

f(i,j)=min{f(i,j),f(i,k) + f(k+1,j) + P[i-1]*P[k]*P[j]}（i=<k<j）

边界为$f(i,i)=0$。

我们使用闫氏DP分析法，实际上我们只需要考虑最后一步的操作即可。

本题我没有找到题目，找到了一道POJ上和这个几乎一模一样的题目，只不过那个题目是输入n只有n个数，所以相当于只有n-1个矩阵，所以会有微小的差别。

所以我们这里的答案是f[1][n - 1]，转移方程的时候也有差别：

f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[i] * a[k + 1] * a[j + 1]); #include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int N = 2007, M = 5000007, INF = 0x3f3f3f3f; int n, m; int f[N][N]; int a[N]; int main() { while(scanf("%d", &n) != EOF && n){ memset(f, 0x3f, sizeof f); for(int i = 1; i <= n; ++ i){ scanf("%d", &a[i]); f[i][i] = 0; } for(int len = 2; len < n; ++ len){ for(int i = 1; i <= n - len; ++ i){ int j = i + len - 1;//注意再 -1 因为三个数才能组成两个可乘矩阵相乘 f[i][j] = INF; for(int k = i; k < j; ++ k) //!相当于是i到j但是需要的是i到j+1：例如第1个和第2个合并，对应到数上就是a[1]a[2]a[3]合并 f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[i] * a[k + 1] * a[j + 1]); } } printf("%d\n", f[1][n - 1]);//终点是 n-1 因为三个数才能组成两个可乘矩阵相乘 } return 0; }