继续创造，加速生长！这是我参与「日新方案 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）中更为明显。假如处理原始问题需求处理一切子问题，一般最好运用表格办法。它编程更简略，速度更快，因为它没有与递归调用相关的开销，并且能够预先分配恰当大小的表，而不是增加备忘录。假如只需求处理一些子问题（一般是这种状况），记忆一般更有用。