动态规划的特征

目录

• 讨论背景
• 分治特点
• 最优子结构
• 自底向上求解
• 子问题复用
• 子问题独立
• 参考文献

讨论背景

为了方便后文举例，此处叙述一下0-1背包问题的定义：

给定一个背包容量W，以及一系列物品 { I 1 , I 2 , . . . , I n } \{I_1, I_2, ... , I_n\} {I1​,I2​,...,In​}；每个物品有各自的重量和价值。要求在背包装得下的情况下，从这一系列物品中选出价值最大的一个组合。
答案用一个数组 C [ 1 : n ] C[1:n] C[1:n]表示， C [ s ] C[s] C[s]只取0或1，分别表示不选 I s I_s Is​或选择 I s I_s Is​。

例如，当W=5，且每个物品的价值如下表所示时，最优选择为 C = { 0 , 1 , 1 } C=\{0, 1, 1\} C={0,1,1}，即只选择物品2和3：

分治特点

虽然我们说起分治策略时，通常想到的是快速排序、二分查找这样的算法，但于动态规划实际上也具有分而治之的色彩，只不过不明显。

例如，对于背包问题，我们可以按顺序依次考虑每个物品。当 C [ 1 ] = 0 C[1]=0 C[1]=0时，所得的子问题是， W = 5 W=5 W=5，考虑的物品则剩下 { I 2 , . . . , I n } \{ I_2, ... , I_n\} {I2​,...,In​}，将这个子问题表示为 P s 0 P_{s0} Ps0​；当 C [ 1 ] = 1 C[1]=1 C[1]=1时，所得的子问题是， W = 5 − 1 = 4 W=5-1=4 W=5−1=4，考虑的物品则是 { I 2 , . . . , I n } \{ I_2, ... , I_n\} {I2​,...,In​}，将这个子问题表示为 P s 1 P_{s1} Ps1​。
与快速排序不同的是，不论 C [ 1 ] C[1] C[1]做何选择，都只能得到一个子问题：要么是 P s 0 P_{s0} Ps0​，要么是 P s 1 P_{s1} Ps1​；与快速排序相同的是，这个子问题比原问题的规模更小，因为，至少我们要考虑的物品已经减少了一个。

实际上，在文献[1]的15.2节的矩阵链乘法（Matrix-chain multiplication）中，每一次确实会划分出两个规模更小的子问题。

最优子结构

还是考虑背包问题。设原问题为 P o P_o Po​，假如我们能为 C [ 1 ] C[1] C[1]做出合适的选择，那么就会得到一个规模更小的子问题 P s P_{s} Ps​，它可能是 P s 0 P_{s0} Ps0​或 P s 1 P_{s1} Ps1​。既然 P o P_o Po​的解用数组 C [ 1 : n ] C[1:n] C[1:n]来表示，那么在做出选择 C [ 1 ] C[1] C[1]之后，待定的就是 C [ 2 : n ] C[2:n] C[2:n]，而这一部分正对应着子问题 P s P_{s} Ps​的解。

如果说 C [ 1 : n ] C[1:n] C[1:n]是 P o P_o Po​的一个最优解，那么 C [ 2 : n ] C[2:n] C[2:n]必然是 P s P_{s} Ps​的一个最优解。否则，假如说 C [ 2 : n ] ′ C[2:n]^\prime C[2:n]′更优，那么将 C [ 1 : n ] = C [ 1 ] + C [ 2 : n ] C[1:n]=C[1]+C[2:n] C[1:n]=C[1]+C[2:n]改写为 C [ 1 : n ] ′ = C [ 1 ] + C [ 2 : n ] ′ C[1:n]^\prime=C[1]+C[2:n]^\prime C[1:n]′=C[1]+C[2:n]′之后， C [ 1 : n ] ′ C[1:n]^\prime C[1:n]′将是一个比 C [ 1 : n ] C[1:n] C[1:n]更优的解，这就与“ C [ 1 : n ] C[1:n] C[1:n]是 P o P_o Po​的一个最优解”这一断言相悖。

这种原问题的最优解包含了子问题的最优解的性质，就是动态规划的标志性特征。说到这里，也许你会觉得这很像贪婪策略。没错，贪婪策略可以说是动态规划的一个特例，但是动态规划有它自己的独特之处，以至于用贪婪策略那种方式来解动态规划问题的话，虽然可以得到正确结果，但时间复杂度却高到不可接受。

自底向上求解

假如用贪婪策略那种自顶向下递归求解的方法，那么我们首先要分别考虑 C [ 1 ] = 0 C[1]=0 C[1]=0和 C [ 1 ] = 1 C[1]=1 C[1]=1的情况，分别导致 P s 0 P_{s0} Ps0​和 P s 1 P_{s1} Ps1​这两个子问题。但是通常情况下，我们没有足够的信息马上判断出来是选择 C [ 1 ] = 0 C[1]=0 C[1]=0并将问题化解为 P s 0 P_{s0} Ps0​更好，还是选择 C [ 1 ] = 1 C[1]=1 C[1]=1并将问题化解为 P s 1 P_{s1} Ps1​更好。因此必须将 P s 0 P_{s0} Ps0​和 P s 1 P_{s1} Ps1​都解决掉，然后比较两种选择所获得的价值。从这里立刻就可见动态规划与贪婪策略的不同之一：贪婪策略往往在解决子问题之前，就能给出一个贪婪选择，但动态规划则需要所有子问题的完整信息才能做出一个最优选择。

P s 0 P_{s0} Ps0​和 P s 1 P_{s1} Ps1​这两个子问题的共同之处就是它们要考虑的物品是 { I 2 , . . . , I n } \{ I_2, ... , I_n\} {I2​,...,In​}，即包括了 I 2 I_2 I2​，因此它们都要决定 C [ 2 ] C[2] C[2]的值。但是与原问题一样，它们也要各自导出两个子问题，然后根据对各自的两个子问题的解来决定 C [ 2 ] C[2] C[2]的值。

现在已经出现4个子问题了。照这样下去，n个物品会导致 O ( 2 n ) O(2^n) O(2n)个子问题的产生。哪怕每个子问题都只对一个物品做出选择与否的决定，因此只需要 O ( 1 ) O(1) O(1)的时间，但是总体上的时间复杂度仍然达到了 O ( 2 n ) O(2^n) O(2n)。

那该怎么办？这时就体现出动态规划的独特性了。动态规划并不会自顶向下递归，而是会从解决子问题 W = 1 , { I n } W=1,\{I_n\} W=1,{In​}开始，然后是 W = 1 , { I n − 1 , I n } W=1,\{I_{n-1},I_n\} W=1,{In−1​,In​}，依次到 W = 1 , { I 1 , . . . , I n − 1 , I n } W=1,\{I_1,...,I_{n-1},I_n\} W=1,{I1​,...,In−1​,In​}。并且每当解决一个子问题，就将它的解记录在一个表里（这是动态规划的必备），可以将这个表称为子问题表。到这一步， W = 1 W=1 W=1时的所有物品已经考虑过了，所以我们将 W W W增加为2，然后从 W = 2 , { I n } W=2,\{I_n\} W=2,{In​}开始，重复上述过程。当然，我这里并非对求解过程的详细描述，而只是一个概述。具体实现需要对边界情况稍加处理，甚至可以以一种不同的方式自底向上。但无论如何，它们肯定都是自底向上。

子问题复用

但是，为什么自底向上？它比自顶向下递归有何优势？当然有，这种求解方法让时间复杂度从 O ( 2 n ) O(2^n) O(2n)降到了 O ( W n ) O(Wn) O(Wn)。这是因为在计算子问题表时，每个表项只需要 O ( 1 ) O(1) O(1)的时间，而既然有 O ( W n ) O(Wn) O(Wn)个表项，那么时间复杂度显然就是 O ( W n ) O(Wn) O(Wn)。

上述论证只适用于背包问题，但是从中可以提取一些见解。你发现没有，实际上真正的子问题只有 O ( W n ) O(Wn) O(Wn)这么多，即每个表项对应一个，那么自顶向下的 O ( 2 n ) O(2^n) O(2n)时间复杂度意味着什么？意味着它在递归的过程中肯定会反复遇到同一个子问题。由于 O ( 2 n ) O(2^n) O(2n)与 O ( W n ) O(Wn) O(Wn)的差异是如此之大，这种反复出现的子问题一定不在少数。相比于每次遇到它们时都将其从头求解一遍，还不如在第一次遇到它们后就将其解保存在一个表里，以后再遇到时就只需要查一下表；而这正是动态规划所做的。

子问题独立

现在立即就要说明一个微妙的地方：虽然重复出现的子问题正是动态规划提高效率的关键，但注意每个子问题必须是相互独立的。这可能容易令人混淆，但其实很简单。考虑两个子问题 P 1 P_{1} P1​和 P 2 P_{2} P2​，说它们会反复出现是指将给定问题分解所得的问题中，它们会反复出现；而说它们必须相互独立是指， P 1 P_{1} P1​的解应当与 P 2 P_{2} P2​的解无关。前者说的是两个子问题的事，后者说的是它们的解的事。至于为什么要提这个要求，我暂时顾不上展开了，你可以去看文献[1]的341-344页。

参考文献

[1] Cormen T H, Leiserson C E, Rivest R L, et al. 算法导论[M]. 2版. 北京：高等教育出版社，2002.