动态规划算法的基本思想（非常详细）
动态规划算法（Dynamic Programming，简称 DP）和前面讲过的分治算法有相似之处，它们都是将问题拆分成很多个简单的小问题，通过逐个解决这些小问题，最终找到整个问题的答案。
也许有读者会问，将问题拆除成很多个小问题，为什么小的问题解决起来就简单呢？可以这样理解，和整个问题要处理的数据量相比，拆除成小的问题以后，每个小问题要处理的数据量减少了，难度自然就降低了。例如找到 100 个整数中的最大值，整个问题可以拆分成 50 个小问题，将 100 个整数分成 50 份，每个小问题只需要找到 2 个整数中的最大值，是不是变简单了。
动态规划算法和分治算法的不同之处在于，分治算法拆分出的小问题之间是相互独立的，而动态规划算法拆分出的小问题之间相互关联，比如要想解决问题 A，必须先解决问题 B 和 C。
接下来，通过一个实例带大家了解动态规划算法。
动态规划算法的解题思路是：用 f(n) 表示凑齐面值 n 所需纸币的最少数量，面值 15 的拼凑方案有 3 种，分别是：
以上 3 种选择方案中，所需纸张数量最少的就是最优的拼凑方案。而想要比较它们，需要继续求 f(14)、f(8)、f(5) 的值。
你看，题目要求计算 f(15) 的值，可以把它拆分成计算 f(14)、f(13)、f(1)、f(4) 等多个小问题，这些小问题之间不是独立的，而是相互关联的，比如 f(14) 的值与 f(13)、f(7)、f(4) 有关，这样的解题思路就叫做动态规划。
f(4)、f(7)、f(13) 等还可以继续拆分，最终会和 f(0)、f(1)、f(2) 产生关联，而 f(0)、f(1)、f(2) 的值是很容易计算的。在得知 f(0)、f(1)、f(2) 等简单问题的结果后，就可以轻松推算出 f(3)~f(14) 的值，进而推算出 f(15) 的值。
这里主要想通过拼凑纸币这个实例，带大家了解动态规划的思想，后续章节会带大家编写代码解决这个问题。总的来说，动态规划算法就是不断地拆分问题，拆分出的这些小问题之间相关关联，通过逐个解决这些简单的小问题，最终就能找到整个问题的答案。
接下来会连续讲解几个实际问题，带大家熟练使用动态规划算法：
此外，弗洛伊德算法在解决最短路径问题的过程中，也用到了“动态规划”的思想，后续章节会给大家做详细地讲解。
也许有读者会问，将问题拆除成很多个小问题，为什么小的问题解决起来就简单呢？可以这样理解，和整个问题要处理的数据量相比，拆除成小的问题以后，每个小问题要处理的数据量减少了，难度自然就降低了。例如找到 100 个整数中的最大值，整个问题可以拆分成 50 个小问题，将 100 个整数分成 50 份，每个小问题只需要找到 2 个整数中的最大值，是不是变简单了。
动态规划算法和分治算法的不同之处在于，分治算法拆分出的小问题之间是相互独立的，而动态规划算法拆分出的小问题之间相互关联，比如要想解决问题 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 所需要的最少的纸币数量。
以上 3 种选择方案中，所需纸张数量最少的就是最优的拼凑方案。而想要比较它们，需要继续求 f(14)、f(8)、f(5) 的值。
f(5) = f(4)+1：选择一张面值为 1 的纸币，再加上 f(4) 的值。
f(8) = f(7) + 1：选择一张面值为 1 的纸币，再加上 f(7) 的值。
f(8) = f(1) +1：选择一张面值为 7 的纸币，再加上 f(1) 的值。
f(14) = f(13)+1：选择一张面值为 1 的纸币，再加上 f(13) 的值。
f(14) = f(7) + 1：选择一张面值为 7 的纸币，再加上 f(7) 的值。
f(14) = f(4) +1：选择一张面值为 10 的纸币，再加上 f(4) 的值。
你看，题目要求计算 f(15) 的值，可以把它拆分成计算 f(14)、f(13)、f(1)、f(4) 等多个小问题，这些小问题之间不是独立的，而是相互关联的，比如 f(14) 的值与 f(13)、f(7)、f(4) 有关，这样的解题思路就叫做动态规划。
f(4)、f(7)、f(13) 等还可以继续拆分，最终会和 f(0)、f(1)、f(2) 产生关联，而 f(0)、f(1)、f(2) 的值是很容易计算的。在得知 f(0)、f(1)、f(2) 等简单问题的结果后，就可以轻松推算出 f(3)~f(14) 的值，进而推算出 f(15) 的值。
这里主要想通过拼凑纸币这个实例，带大家了解动态规划的思想，后续章节会带大家编写代码解决这个问题。总的来说，动态规划算法就是不断地拆分问题，拆分出的这些小问题之间相关关联，通过逐个解决这些简单的小问题，最终就能找到整个问题的答案。
动态规划算法的实际应用
动态规划是一种很常用的算法，它能够将复杂的问题拆分成很多小问题，这些小问题之间相互关联，解决掉所有的小问题，就可以轻松得到整个问题的答案。接下来会连续讲解几个实际问题，带大家熟练使用动态规划算法：
此外，弗洛伊德算法在解决最短路径问题的过程中，也用到了“动态规划”的思想，后续章节会给大家做详细地讲解。
ICP备案：
公安联网备案：