持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第31天，点击查看活动详情

动态编程

动态编程是由理查德·贝尔曼在 1950 年代发明的。不要试图从它的名字中推断出任何关于这项技术的信息。正如贝尔曼所描述的那样，选择“动态编程”这个名字是为了向政府赞助商隐瞒“我真的在做数学的事实......[动态编程这个短语]是连国会议员都无法反对的。94.

动态规划是一种有效解决具有重叠子问题和最优子结构特征的问题的方法。幸运的是，许多优化问题都表现出这些特征。

如果通过将局部子问题的最优解组合在一起可以找到全局最优解，则问题具有最优子结构。我们已经研究过一些这样的问题。例如，合并排序利用了这样一个事实，即可以通过首先对子列表进行排序，然后合并解决方案来对列表进行排序。

如果最优解决方案涉及多次解决同一问题，则问题具有重叠的子问题。合并排序不显示此属性。尽管我们多次执行合并，但每次都会合并不同的列表。

这不是很明显，但 0/1 背包问题表现出这两种特性。然而，首先，我们跑题看一个最优子结构和重叠子问题更明显的问题。

重新审视 斐波那契数列

在第4章中，我们研究了斐波那契函数的简单递归实现：

虽然这种重复实现显然是正确的，但它的效率非常低。例如，尝试运行 fib（120），但不要等待它完成。实现的复杂性有点难以推导，但它大致是o（fib（n））。也就是说，它的增长与结果值的增长成正比，斐波那契数列的增长率是可观的。例如，fib（120） 为 8，670，007，398， 507，948， 658，051，921。如果每个递归调用需要一纳秒，fib（120） 大约需要 250，000 年才能完成。

让我们尝试弄清楚为什么此实现需要这么长时间。鉴于fib主体中的代码量很小，很明显，问题一定是fib调用自己的次数。例如，查看与调用 fib（6） 关联的调用树。

请注意，我们一遍又一遍地计算相同的值。例如，fib 被调用 3 三次，每次调用都会引发 4 次额外的 fib 调用。它不需要天才地认为，记录第一次调用返回的值，然后查找它而不是每次需要时计算它可能是一个好主意。这是动态规划背后的关键思想。

动态规划有两种方法

记忆自上而下解决了原始问题。它从原始问题开始，将其分解为子问题，将子问题分解为子问题，等等。每次它解决一个

子问题，它将答案存储在表中。每次需要解决一个子问题时，它首先尝试在表中查找答案。

表格是一种自下而上的方法。它从最小的问题开始，并将问题的答案存储在表中。然后，它将这些问题的解决方案组合在一起，以解决下一个最小的问题，并将这些答案存储在表中。

图 15-2 包含使用每种动态规划方法的斐波那契实现。函数 fib memo 有一个参数 memo，它用来跟踪它已经评估过的数字。该参数有一个默认值，即空字典，因此 fib memo 的客户端不必担心为 memo 提供初始值。当使用 n > 1 调用 fib_memo 时，它会尝试在备忘录中查找 n。如果它不存在（因为这是第一次使用该值调用fib_memo），则会引发异常。发生这种情况时，fib_备忘录使用正常的斐波那契重复周期，然后将结果存储在备忘录中。

fib_tab的功能非常简单。它利用了斐波那契的所有子问题都是预先知道的，并且易于以有用的顺序枚举的事实。

如果你尝试运行 fib_memo 和 fib_tab，你会发现它们确实非常快：fib（120） 几乎立即返回。这些功能的复杂性是什么？FIB 备忘录对从 O 到 N 的每个值只调用 FIB 一次。因此，在字典查找可以在常量时间内完成的假设下，fib_备忘录（n）的时间复杂度在o（n）中。fib_tab在o（n）中更为明显。如果解决原始问题需要解决所有子问题，通常最好使用表格方法。它编程更简单，速度更快，因为它没有与递归调用相关的开销，并且可以预先分配适当大小的表，而不是增加备忘录。如果只需要解决一些子问题（通常是这种情况），记忆通常更有效。