1、动态规划算法基本思想： 与分治法类似，也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 2、基本步骤： 1）找出最优解的性质，并刻划其结构特征。 2）递归地定义最优值。 3）以自底向上的方式计算出最优值。 4）根据计算最优值时得到的信息，构造最优解。 3、矩阵连乘问题： 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 给定n个矩阵{A1,A2,A3,…,An}， 其中Ai与Ai+1是可乘的，其中i=1,2,…,n-1.考察这n个矩阵的连乘积 A1A2…An 如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 1）穷举法： 列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 2）动态规划： 将矩阵连乘积Ai,Ai+1,…,Aj 简记为A[i:j] ，这里i≤j .考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则相应完全加括号方式为(AiAi+1…Ak)(Ak+1Ak+2…An) 计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量。 4、问题求解分析： 1）分析最优解 计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。 2）建立递归关系： 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]； 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n ； 当i<j时，m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j] 这里 Ai 的维数为p[i-1]*p[i] ; 可以递归地定义m[i,j]为：其中k的位置只有 j-i 种可能 3）计算最优值： 对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。
5、算法实现：
public class Matrix { public static void main(String[] args) { // TODO Auto-generated method stub int p[]=new int[]{30,35,15,5,10,20,25}; int m[][]=new int[4][4]; int s[][]=new int[4][4]; matrixChain(p,m,s); traceback(s,0,3); } private static void matrixChain(int[]p,int[][]m,int[][]s){ int n=m.length; for(int i=1;i<n;i++){ m[i][i]=0; } for(int r=2;r<=n;r++){ 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]; s[i][j]=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; } } } } } public static void traceback(int[][]s,int i,int j){ if(i==j) {return;} else if(i<j){ traceback(s,i,s[i][j]); traceback(s,s[i][j]+1,j); System.out.println("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+1)+","+j); } } }6、算法复杂度分析： 算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。
