动态规划算法解决问题的过程和分治算法类似，也是先将问题拆分成多个简单的小问题，通过逐一解决这些小问题找到整个问题的答案。不同之处在于，分治算法拆分出的小问题之间是相互独立的，而动态规划算法拆分出的小问题之间相互关联，例如要想解决问题 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) 没有对应的值，我们用 ∞ 表示它们的值：
表 1 不选择任何纸币
|
选择的纸币 |
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 所示：
表 2 选择面值为 1 的纸币
|
选择的纸币 |
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 |
3) 使用面值为 7 的纸币，可以对表 2 中各个拼凑方案做进一步优化：
表 3 选择面值为 7 的纸币
|
选择的纸币 |
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 进行优化：
表 3 选择面值为 10 的纸币
|
选择的纸币 |
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 背包问题则可以用动态规划算法解决。
此外，弗洛伊德算法在解决最短路径问题的过程中，也用到了“动态规划”的思想，后续章节会给大家做详细地讲解。
本文链接：http://task.lmcjl.com/news/14249.html
