1.动态规划与分治法最大的区别是：所分解的子问题不是相互独立的；动态规划对每个子问题只计算一次，将其结果保存到表中，避免再次遇到子问题的情况下重复计算，是一种空间换时间的办法。
2.矩阵链相乘
（1）A1A2A3A4A5五个矩阵相乘，可以根据加括号的位置得到不同的计算过程如 A1（A2A3）A4A 5 和A1A2A3（A4A5），计算过程决定计算复杂度；
（2）若A是p*q的矩阵，B是q*r的矩阵，那么乘积C一定是p*r的矩阵。三个矩阵A,B,C，假设规模分别为10X100, 100X5, 5X50。如果先按照((AB)C)，需要的乘法次数为：10*100*5 + 10*5*50 = 7500；如果按照(A(BC))，需要的乘法次数为：100*5*50 + 10*100*50 = 75000。可见第一种结合方法的计算速度是第二种的10倍。
3.动态规划思想：
（1）m[i,j]表示矩阵Ai到Aj之间需要的乘法次数的最小值，这里i < j且中间不会有断点，如 i=1，j=4，则表示A1*A2*A3*A4；
（2）在 i 和 j 之间的最佳分割点已经知道，它的值就是k，满足，i <= k < j；现在我们还有一个已知条件，也是唯一的一个条件：矩阵Ai的规模为Pi-1 X Pi，有一个序列 P = [P0,P1,P2,…,Pn]
（3）矩阵B=i~k的矩阵相乘，C=k+1~j的矩阵相乘，那么矩阵i~j相乘=B*C。即有m[i,j]=m[i,k]=m[k+1,j]+Pi-1PkPj ， m[i,j] = m[i,k] + m[k+1,j] + P[i-1]*P[k]*P[j]
当i=j时表示只有一个矩阵一组m[i,j]=0;
m[i][j]表示矩阵Ai~Aj的最小相乘次数，s[i][j]表示矩阵Ai~Aj之间的最佳括号k的位置
/** * */ package matrixChain; /** * @author LingLee *矩阵链相乘问题 */ public class MatrixChain { private int[] p;//矩阵维度p0~pn； private int len;//矩阵的个数，此处len=p.len-1 private int[][] m;//矩阵i~j的最小计算次数 private int[][] s;//矩阵k的位置 public MatrixChain(int[] p,int len){ this.p=p; this.len=len; m=new int[p.length ][p.length]; s=new int[p.length][p.length]; } public void compute(){ if(p==null||len==0) return ; //int k; int min;//最小计算次数 for(int i=0;i<p.length;i++) m[i][i]=0;//长度为1的矩阵链计算次数为0,0<<i<<n for(int l=2;l<=len;l++){//l表示矩阵链长度 从2到len, len=n即n个矩阵 for(int i=1;i<=p.length-l;i++){//0<<i<<pn,即n+1个元素 int j=i+l-1;// m[i][j]=Integer.MAX_VALUE; for(int k=i;k<j;k++){//i~j之间最佳括号位置 int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(q<m[i][j]) { m[i][j]=q; s[i][j]=k; // System.out.println("m[i,j]="+q); // System.out.println("s[i,j]="+q); } } } } } public void printM(){ for(int i=0;i<m.length;i++){ for(int j=0;j<m.length;j++){ if(i<j&&i>0){ System.out.println("m["+i+"]["+j+"]="+m[i][j]); } } } System.out.println("最优运算次数:"+m[1][m.length-1]); } public void printS(int i,int j){ if(i==j) System.out.print("A"+i); else{ System.out.print("("); printS(i,s[i][j]);//s[i][j]存的是k的值，此处递归打印i~k,和K+1~j printS(s[i][j]+1,j); System.out.print(")"); } } public static void main(String[] args){ int p[] = { 30, 35, 15, 5, 10, 20, 25 }; int p1[] = { 5, 10, 3, 12, 5, 50, 6 }; MatrixChain mcChain=new MatrixChain(p, p.length); mcChain.compute(); mcChain.printM(); mcChain.printS(1,p.length-1); } }
