首页 > 编程笔记
动态规划算法
动态规划算法解决问题的过程和分治算法类似，也是先将问题拆分成多个简单的小问题，通过逐一解决这些小问题找到整个问题的答案。不同之处在于，分治算法拆分出的小问题之间是相互独立的，而动态规划算法拆分出的小问题之间相互关联，例如要想解决问题 A，必须先解决问题 B 和 C。
《贪心算法》一节中，给大家举过一个例子，假设有 1、7、10 这 3 种面值的纸币，每种纸币使用的数量不限，要求用尽可能少的纸币拼凑出的总面值为 15。贪心算法最终给出的拼凑方案是需要 10+1+1+1+1+1 共 6 张纸币，而如果用动态规划算法解决这个问题，可以得出最优的拼凑方案，即只需要 1+7+7 共 3 张纸币。
动态规划算法的解题思路是：用 f(n) 表示凑齐面值 n 所需纸币的最少数量，面值 15 的拼凑方案有 3 种，分别是：
- f(15) = f(14) +1：挑选一张面值为 1 的纸币，f(14) 表示拼凑出面值 14 所需要的最少的纸币数量；
- f(15) = f(8) + 1：挑选一张面值为 7 的纸币，f(8) 表示拼凑出面值 8 所需要的最少的纸币数量；
- f(15) = f(5) + 1：选择一张面值为10 的纸币，f(5) 表示拼凑出面值 5 所需要的最少的纸币数量。
也就是说，f(14)+1、f(8)+1 和 f(5)+1 三者中的最小值就是最优的拼凑方案。采用同样的方法，继续求 f(14)、f(8)、f(5) 的值：
- f(5) = f(4) + 1；
- f(8) = f(7) + 1 = f(1) +1；
- f(14) = f(13)+1 = f(7) + 1 = f(4) +1。
感兴趣的读者还可以继续拆分 f(4)、f(7)、f(13) 等。经过不断地拆分，f(15) 最终会和 f(0)、f(1)、f(2) 等产生关联，而 f(0)、f(1)、f(2) 的值是很容易计算的。在得知 f(0)、f(1)、f(2) 等简单问题的结果后，就可以轻松推算出 f(3)~f(14) 的值，最终可以推算出 f(15) 的值。
对于每种纸币来说，是否使用它可能会影响 f(n) 的值。接下来，我们就一一分析三种纸币对 f(0)~f(15) 的影响：
1) 在不能使用任何纸币的情况下，f(1)~f(15) 没有对应的值，我们用 ∞ 表示它们的值：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 不选择任何纸币 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
2) 使用面值为 1 的纸币，可以对表 1 中各个拼凑方案对应的值进行优化，如表 2 所示：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 选择面值为 1 的纸币 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
f(1)~f(14) 对应的值都可以优化，计算方式是：f(1)=f(0)+1，f(2)=f(1)+1，f(3)=f(2)+1... f(15)=f(14)+1 。
3) 使用面值为 7 的纸币，可以对表 2 中各个拼凑方案做进一步优化：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 选择面值为 7 的纸币 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 2 | 3 |
f(0)~f(6) 中无法使用面值为 7 的纸币，而 f(7)~f(15) 可以选择面值为 7 的纸币，它们各自产生了更优的解决方案：f(7)=f(0)+1，f(8)=f(1)+1，...，f(15)=f(8)+1。以 f(7) 为例，除了使用先前的 f(6)+1 方案，还可以选择 f(0)+1 方案，显然后者更优，只需要一张纸币。
4) 使用面值为 10 的纸币，继续对表 3 进行优化：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 选择面值为 10 的纸币 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 3 |
对比表 2 不难发现，面值为 10 的纸币仅对 f(10)~f(13) 起到了优化的作用，而对于 f(14) 和 f(15) 来说，选择面值为 10 的纸币，并没有先前的解决方案好。最终，f(15) 的最优拼凑方案是只需要 3 张纸币（7+7+1）。
以上我们解决问题所用的方法就是动态规划算法。总的来说，动态规划算法就是不断地拆分问题，拆分出的这些小问题之间相关关联，通过解决一些简单的问题，复杂的问题也能迎刃而解。
动态规划算法的实际应用
《贪心算法》一节提到，背包问题的种类有很多，其中部分背包问题可以用贪心算法解决，而 0-1 背包问题则可以用动态规划算法解决。此外，弗洛伊德算法在解决最短路径问题的过程中，也用到了“动态规划”的思想，后续章节会给大家做详细地讲解。
