高效的动态规划算法 _动态规划算法

选自medium
作者：Meet Zaveri
机器之心编译
参与：曾祥极、张倩

乔治·桑塔亚纳说过，“那些遗忘过去的人注定要重蹈覆辙。”这句话放在问题求解过程中也同样适用。不懂动态规划的人会在解决过的问题上再次浪费时间，懂的人则会事半功倍。那么什么是动态规划？这种算法有何神奇之处？本文作者给出了初步的解答。

假设你正在使用适当的输入数据进行一些计算。你在每个实例中都进行了一些计算，以便得到一些结果。当你提供相同的输入时，你不知道会有相同的输出。这就像你在重新计算之前已经计算好的特定结果一样。
那么问题出在哪里呢？你之前计算某些结果的宝贵时间被浪费掉了。你可以通过保存之前的计算结果去轻易地解决这个问题。比如通过使用恰当的数据结构。举个例子，你可以将输入输出作为键值对映射保存起来。

那些遗忘过去的人注定要重蹈覆辙 ~ 动态规划

现在通过分析这个问题，我们可以将新的输入（或者不在数据结构中的输入）与其对应的输出存储下来。或者在字典中查找输入并返回相应的输出结果。这样当你在进行一些计算时，你可以检查数据结构中是否存在该输入，如果数据输入存在的话就可以直接获得结果。我们将与这种方法相关的技巧称作动态规划。
详解动态规划
现在让我们更详细地介绍动态规划。
简而言之，我们可以说动态规划主要用来解决一些希望找到问题最优解的优化问题。
一种可以用动态规划解决的情况就是会有反复出现的子问题，然后这些子问题还会包含更小的子问题。相比于不断尝试去解决这些反复出现的子问题，动态规划会尝试一次解决更小的子问题。之后我们可以将结果输出记录在表格中，我们在之后的计算中可以把这些记录作为问题的原始解。
举个例子，斐波那契数列 0,1,1,2,3,5,8,13,…有着一个相当简单的描述方式，它的每个数字都与前两个紧邻的数字相关。如果 F(n) 是第 n 个数字，那么我们会有 F(n) = F(n-1) + F(n-2) 。这个在数学上称作*递归方程*或者*递推关系* 。为了计算后面的项，它需要前面项的计算结果作为输入。

文章插图

大多数动态规划问题都能被归类成两种类型：
大多数动态规划问题都能被归类成两种类型：

优化问题
组合问题

优化问题希望你选择一个可行的解决方案，以便最小化或最大化所需函数的值。组合问题希望你弄清楚做某事方案的数量或某些事件发生的概率。
解决方案的对比：自上而下或者自下而上
以下是两种不同的动态规划解决方案：

自上而下：你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（*Memoization*）。
自下而上：你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（*Tabulation，*table-filling algorithm**）。

至于迭代和递归与这两种方法的关系，自下而上用到了迭代技术，而自上而下则用到了递归技术。

文章插图

图片中的展示在理论上可能并不完全正确，但这是一种可以理解的展示方式。
这儿有一个普通方法和动态规划方法的比较，你可以看到两者时间复杂度的不同。
Memoization 的准则：不要忘记
Jeff Erickson 在他的笔记中这样描述斐波那契数列：
递归算法之所以速度慢，是因为它一遍又一遍地计算了相同的斐波那契数列。