摘要

究竟什么时候才需要动态规划？这里介绍两个要素：最优子结构，重叠子问题。另外，还要分析一种方法——备忘录，充分利用重叠子问题性质。

最优子结构

利用动态规划求解时第一步是描述最优解的结构。当一个问题具有最优子结构时，提示我们动态规划可能会适用。

在寻找最优子结构时，可以遵循一种共同的模式：
1）问题的一个解可以是一个选择；
2）假设对于一个给定问题，已知的是一个可以导致最优解的选择；
3）在已知这个选择后，要确定哪些子问题会随之发生。

最优子结构在问题域中以两种形式变化：
1）有多少个子问题被使用在原问题的一个最优解中；
2）在决定一个最优解中使用哪些子问题时有多少个选择。

非正式地，一个动态规划算法的运行时间依赖两个因素的乘积：子问题总个数和每一个子问题有多少选择。

动态规划以自底向上的方式来利用最优子结构。首先找到子问题的最优解，解决子问题尔后解决原问题。贪心算法与动态规划有一个显著的差别：贪心算法是自顶向下的方式使用最优子结构。贪心算法会先做在当时看起来是最优的选择，然后再求借一个结果的子问题。而不像动态规划，先找子问题最优解，然后再做选择。

注意：在不能应用最优子结构的时候，一定不能假设它能够应用。考虑如下两个问题：无权最短路径和无权最长简单路径。论证部分略，但无权最短路径问题具有最优子结构，而最长简单路径不仅缺乏最优子结构，而且也无法根据子问题的解来构造原问题合法的解（会产生循环路径）。事实上，最长简单路径是NPC问题，即NP完全问题，即不可能在多项式时间内解决。

产生这个问题的原因在于寻找最长简单路径子问题不是独立的，是否独立意味着一个子问题的解会不会影响同一问题中另一个子问题的解。当子问题不独立时，对一个子问题的处理会影响另一个子问题，因而无法求解。

重叠子问题

动态规划要求子问题的空间要小。也就是用来接解原问题的递归算法可以反复地解同样的子问题，而不是总在产生新的子问题。当一个递归算法不断地调用同一个问题时，我们说该最优问题包含重叠子问题。相反地，分治法在解决问题时每一步都会产生全新的问题。将子问题存入表中，每次查询只需要常数时间。

重新构造一个最优解

在实际应用中，我们通常把每一个子问题所做的选择保存在一个表中，在需要时查表获取信息重构最优解。

在装配线问题中，在l_i[j]中保存通过S_i,j的最快路线中S_i,j的前一站。对于装配线问题，即使没有表格，重构装配站也只需要O(1)时间。

对于矩阵链乘法，重构最优解时，有了记录选择的表s[i,j]就可以少做很多工作。

做备忘录

动态规划有一种变形，具有通常动态规划的效率，但是采用了自顶向下的策略。其思想就在于备忘原问题的递归算法，像动态规划一样维护一个记录子问题解的表。

一般而言自底向上的动态规划比自顶向下的备忘录好处一个常数因子，因为无需递归的代价。但是如果子问题空间中某些字问题没有必要求解，做备忘录只求必要子问题就具备了优势。

[CLRS][CH 15.3] 动态规划基础