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

一个$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;
}