动态规划算法详解
- 作者: 那晚越女说我?
- 来源: 51数据库
- 2022-09-22
既分治算法和贪心算法之后，本节再给您介绍一种常用的算法——动态规划算法。
和分治算法类似，动态规划算法也是先将问题分解成多个规模更小、更容易解决的小问题，通过解决这些小问题，从而找到解决整个问题的方法。不同之处在于，分治算法分解的每个小问题都是相互独立的，而动态规划算法分解的小问题之间往往存在关联，比如要想解决问题 A 和问题 B，必须先解决问题 C。
讲解贪心算法时，我们举过一个例子：假设有 3 种面值分别为 1、7 和 10 的硬币，要求用尽可能少的硬币拼凑出的总面值为 15。贪心算法的解决方案为共需要 6 枚硬币（10+1+1+1+1+1），但如果采用动态规划算法，可以找到更优的解决方案，只需要 3 枚硬币（ 7+7+1）。
动态规划算法的解题思路是：用 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(15) 的值，转换成为了求 min( f(14) , f(8) , f(5) ) 的值（min() 表示取三者中的最小值）。在此基础上，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(0) 或 f(1) 这类很简单的子问题。也就是说，我们只需要求得 f(0) 和f(1) 的值，所有小问题都可以得到解决（如表 1 所示）。
| 子问题 | 分解方案 | 最佳方案 | 硬币数量 |
|---|---|---|---|
| f(0) | 不可再分 | 不选择任何硬币 | 0 |
| f(1) | f(0) + 1 | "1" | 1 |
| f(2) | f(1) + 1 | "1+1" | 2 |
| f(3) | f(2) + 1 | "1+1+1" | 3 |
| f(4) | f(3) + 1 | "1+1+1+1" | 4 |
| f(5) | f(4) + 1 | "1+1+1+1+1" | 5 |
| f(6) | f(5) + 1 | "1+1+1+1+1+1" | 6 |
| f(7) | f(6) + 1 , f(0) + 1 | "7" | 1 |
| f(8) | f(7) + 1 , f(1) + 1 | "7+1" | 2 |
| f(9) | f(8) + 1 , f(2) + 1 | "7+1+1" | 3 |
| f(10) | f(9) + 1 , f(3) + 1 , f(0) + 1 | "10" | 1 |
| f(11) | f(10) + 1 , f(4) + 1 , f(1) + 1 | "10+1" | 2 |
| f(12) | f(11) + 1 , f(5) + 1 , f(2) + 1 | "10+1+1" | 3 |
| f(13) | f(12) + 1 , f(6) + 1 , f(3) + 1 | "10+1+1+1" | 4 |
| f(14) | f(13) + 1 , f(7) + 1 , f(4) + 1 | "7+7" | 2 |
| f(15) | f(14) + 1 , f(8) + 1 , f(5) + 1 | "7+7+1" | 3 |
表 1 中借助 f(0) 和 f(1) 的值，依次推导出了 f(2)~f(15) 的值。因此，我们可以很容易得出“拼凑总面值为 15 只需要 7+7+1 共 3 个硬币”的最佳解决方案，这样解决问题的方法就称为动态规划算法。
动态规划算法的实际应用
如下给您列举了几个适合采用动态规划算法解决的经典案例：
0-1背包问题；
弗洛伊德算法解决最短路径问题；
最长公共子序列问题；
我们会在后续的文章中，一一为您讲解如何用动态规划算法解决这些问题。
