特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
如计算 A1*A2*A3*A4*A5*A6
/**
int [] p 存放各个矩阵的列
int [][] m 所需要的最少数乘次数m[i,j] 1≤i≤j≤n, 最后乘法次数为 m[1][n];
int [][] s s[i][j]:存放的值为相对于m[i][j] 的断开位置
*/
void matrixChain(int [] p, int [][] m, int [][] s)
{
for (int i = 1; i <= n; i++) m[i][i] = 0; //自身相乘，次数为0
for (int r = 2; r <= n; r++) //先计算2个矩阵相乘次数，然后3个，4个...
for (int i = 1; i <= n-r+1; i++) { //
int j=i+r-1; //当前矩阵总个数
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; //m[i][j]初始化为 从i分割 ，实际还加了m[i][i],为0
s[i][j] = i; //从i分割
for (int k = i+1; k < j; k++) { //枚举每个位置 为分割点
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;}
}
}
}
下面这种方法在 书上叫 备忘录 ；
这种方法是自顶向下的
int lookupChain(int i,int j){
if(m[i][j]>0) return m[i][j];
if(i==j) return 0;
m[i][j] = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
for(int k=i+1; k<j; k++){
int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
if(t<m[i][j]) m[i][j] = t;
}
return m[i][j];
}