动态规划算法

 

动态规划算法解决问题的过程和分治算法类似,也是先将问题拆分成多个简单的小问题,通过逐一解决这些小问题找到整个问题的答案。不同之处在于,分治算法拆分出的小问题之间是相互独立的,而动态规划算法拆分出的小问题之间相互关联,例如要想解决问题 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
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 中各个拼凑方案做进一步优化:

表 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 背包问题则可以用动态规划算法解决。

此外,弗洛伊德算法在解决最短路径问题的过程中,也用到了“动态规划”的思想,后续章节会给大家做详细地讲解。

关注公众号「站长严长生」,在手机上阅读所有教程,随时随地都能学习。本公众号由站长亲自运营,长期更新,坚持原创,专注于分享创业故事+学习历程+工作记录+生活日常+编程资料。

公众号二维码
微信扫码关注公众号