4.2 动态规划算法分析

动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种具体算法。因此，必须对待解决的具体问题进行具体分析，先运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。在上一节中，以最长公共子序列为例，给出了如何用动态规划思想求解最优化问题。这一节，将从抽象的角度来分析什么样的问题可以用动态规划思想求解，并介绍动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

4.2.1 最优子结构

用动态规划优化问题的第一步是描述最优解的结构。当一个问题具有最优子结构时，动态规划思想就可能适用于解决该问题（在这种情况下，贪心策略可能也是适用的，后续章节会介绍贪心策略）。最优子结构性质可以表述为：问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态的最优决策。

也就是说，在动态规划中，利用子问题的最优解可以得到原问题的最优解，因此在设计算法时，必须认真分析，确保所考虑的子问题范围中，要包含用于最优解中的那些子问题。

上一节的最长公共子序列问题就具有最优子结构性质，两个序列X和Y的最长公共子序列可以通过这两个序列的前缀间（“X_m-1和Y_n-1”或“X_m-1和Y”或“X和Y_n-1”）的最长公共子序列来构造。在寻找一个问题的最优子结构时，可以采用以下思路求解。

1）试着将待解决问题抽象为做选择的问题，做这种选择会得到一个或多个有待解决的子问题。

2）假设这个待解决问题已经有已知的可以得到最优解的选择，暂且不关心这个选择是如何确定的。

3）已知这个选择后，分析会出现哪些待解决的子问题，并试着恰当地描述这些子问题。

4）证明在待解决问题的一个最优解中，使用的子问题的解本身也是子问题的最优解。

下面用一个简单的例子对上面的思路作进一步的说明。假设现在有一个有向图G=(V,E)和结点u, v∈V。要求找出一条从u到v的包含最少边数的路径。这样的一条路径必须是简单路径，因为从路径中去掉一个回路后，会产生边数更少的路径。这个问题被称为无权最短路径。

首先假设u≠v，这样任意从u到v的路径p必然包含一个中间顶点w。这个问题其实等价于判断这个有向图中每一个顶点是否在路径p上，因此得到了一个选择问题，即是否选择某顶点作为最短路径上的一个顶点。下一步，可以假设顶点w在这条最短路径p上（暂且不关心这个结论是如何确定的），那么路径p就可以分解为两条子路径，即从顶点u到w的子路径p1和从顶点w到v的子路径p2。那么就将解决原问题变成了解决两个子问题。现在就需要证明路径p1和路径p2是否必须是顶点u到w和顶点w到v的无权最短路径，如果是的话，那么就说明这个问题的最优解中包含的子问题的解也是最优解（该证明很容易，故不在此赘述）。可以考虑使用动态规划思想解决。实际上，通常要考虑所有的中间顶点w，先找出从u到w的一条最短路径和从w到v的一条最短路径，然后选择一个会产生整体最短路径的中间结点w，从而找出从u到v的一条最短路径。

4.2.2 重叠子问题

动态规划求解的最优化问题必须具备的第二个要素是重叠子问题。重叠子问题指的是：在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些问题已经被反复计算多次。对于这些会被求解多次的子问题，在动态规划算法中，对这些子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，不必重新求解。

以上一节中介绍的最长公共子序列为例，在解c[m,n]时，由递归式可知需要反复查看参数较小的子问题的解。例如给出序列X=<A,B,C,B,D,A,B>与序列Y=<B,D,C,A,B,A>，按照递归的思路，计算c[7,6]时，需要调用四次c[4,2]，如果c[4,2]每次都被重新计算，而不是被查看，则所增加的运行时间相当可观。事实上，可以证明由递归程序直接来计算c[m,n]的运行时间为O(2^mn)。然而，如果使用自底向上的动态规划算法，那么可以发现解c[m,n]时，因为最多有m⋅n个子问题，从表4.1中可知，每个子问题只会被计算一次，计算每个子问题的时间为O(1)，因此，用动态规划解LCS的运行时间为O(mn)。