今天又认真看了算法导论中的动态规划原理那一节， 有一点想法。
书中说的适合动态规划解决的问题有两个要素：最优子结构和子问题重叠。后者就有记忆化搜索这个没什么好讲的。那么关于最有子结构，其实当我们在猜测最优子结构时，一般有两个问题：一是我们要把规模为n的问题变成小于n的子问题；二是我们要合并小于n的这些子问题的解。这里我主要想讨论的是合并子问题时的一些问题。
举个例子《算法导论》15.2中提到的矩阵链乘法，我们用M（i,j）来记录Ai,Ai+1,……Aj的计算代价，那么求A1,A2,……Aj？我们假如从k和k+1初切割子问题能得到最优解，那么代价即为M（1，k）+M（k+1，j）再加上两个子问题合并的代价，即A1的行*Ak的列*Aj的列。这里注意：无论我们如何求解这两个子问题，A1的行*Ak的列*Aj的列这个值是永远不会变的。这就是我想讨论的重点：求解子问题，对合并子问题没有影响。这也是动态规划的一个要素！！
原文：http://www.cnblogs.com/chaiwentao/p/4357423.html