eclipse-luna
win7_64bit
jdk1.7.5
寻找最优子结构
构造递归解设m[i,j]为矩阵链Ai...Aj的最优解的代价，则 ┌ 0 如果i = jm[i,j] = │ └ min(i≤k＜j) {m[i,k] + m[k+1,j] + Ai.row*Ak.col*Aj.col} 如果i ＜ j
构建辅助表，解决重叠子问题 从第二步的递归式可以发现解的过程中会有很多重叠子问题，可以用一个nXn维的辅助表t[n][n]来保存子问题的解，表中每个元素包含2个信息，分别是最优乘积代价及其分割位置k。辅助表t[n][n]可以由2种方法构造，一种是自底向上填表构建，该方法要求按照递增的方式逐步填写子问题的解，也就是先计算长度为2的所有矩阵链的解，然后计算长度3的矩阵链，直到长度n；另一种是自顶向下填表的备忘录法，该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值)，以表示待计算，在递归的过程中逐个填入遇到的子问题的解。 备忘录法会比自底向上法慢一个常数因子，因为前者有递归调用的代价，维护表格的开销也稍大。
java源代码：package ch3.dynamic.algorithm;public class MatrixChain { public static Pair matrixChainOrder(int[] p){ int n=p.length-1; int i,j,L,k,q; int[][] m = new int[n+1][n+1]; int[][] s = new int[n+1][n+1]; for(i=0;i<=n;i++){ m[i][i]=0; } for(L=2;L<=n;L++){ ///L是子矩阵链的长度 for(i=1;i<=n-L+1;i++){ ///这个地方n也算是一个 eg 6-2+1=5 5,6 就是一组 j=i+L-1; ///这个地方我们可以分析得 j-L+1=i 类似于上面一行的说明解释 m[i][j]=Integer.MAX_VALUE; ///预先设置m[i][j]等于无穷大 for(k=i;k<=j-1;k++){ q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; ///用于暂时存储i-j子矩阵链中的求解的值 //////由于全部加括号 那么相互之间构成括号结合的两项肯定是相互靠近在一起的两项 if(q
运行测试成功效果：
感觉不错请投票支持奥
这个地方学了一个下午自我感觉比较难理解，主要是很多算法思想是第一次接触