动态规化算法与备忘录方法的基本思想

    动态规化算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于动态规化算法来解的问题，经分解后这些子问题往往不是互相独立的。如果用递归的方式进行，这些子问题有可能多次重复计算，所以我们可以用一个表来记录所有已解决的子问题。

    动态规化算法的基本要素：
(1): 最优子结构
(2): 重叠子问题

    设计一个动态规化算法，通常可以按以下几个步骤进行：
(1): 找出最优解的性质，并刻画其结构特征。
(2): 递归地定义最优值
(3): 以自底向上的方式计算出最优解
(4): 根据计算最优解时得到的信息，构造一个最优解。

    递归算法一般比非递归算法要简洁，前面动态规化算法是用一个表格来保存已经解决了的子问题，我们可以在下次需要解此子问题的时候，首先查看其是否已经计算过，如果计算过了，就直接返回结果，从而避免相同子问题的重复求解，这就是备忘录方法的基本思想。

    现在我们从书中的几个例子来推测递归定义的构造。可以看到，它们都具有D(i,j)的形式，虽然其中的i,j含义各不相同。当i,j取不同的值的时候，则构成它们的子序列。比如矩阵连乘问题，D(i,j)分别代表第i个矩阵到第j个矩阵的的最少计算次数，当其取0,5的时候，则是问题的解；最长公共子序列则是第一个数组元素为i，第二个数组元素为j时的最长公共子序列，当其分别取最后一个元素时，则是问题的解；0-1背包问题则对应于背包的容量和现在所取的物品号。当然限制条件也有可能是三个及以上。也许可以这么看，比如0-1背包问题，其具体例子的最终要求是求背包容量为10，从第1个元素开始选择，能得到的最大价值？把这里的数字替换成i和j则是一般形式中的i,j的含义。