什么是动态规划（Dynamic Programming）？动态规划的 ...

franciscochonge · 发表于 2022-3-16 10:51

本系列的主旨是让复杂的问题变得通俗易懂。有些问题乍看起来可能非常吓人。如何才能真正地去理解问题的本质，并在此基础上，令复杂的计算机科学看起来有趣、易懂，从而不会让人心生恐惧，是本系列的要实现的效果，从之前写过的文章来看，我们已经做到了这一点，沾沾自喜一下。
在以往的文章来看，我们也已经通过多种方式为所涉及的每个主题进行了简单化。我们剖析了复杂的数据结构，如[[堆栈]]和[[队列]]，将它们分解成[[链表]]。我们通过理解和慢慢地、系统地建立在小部件的基础上，来研究复杂的算法，这些复杂的算法都是基于这些小部件的。
嗯，你猜怎么着？这种策略远非独一无二。事实上，它是计算机科学世界中最常用的解决问题的方法之一！将一个问题分解成更小的问题。将一个问题分解成更小、更小的部分，是计算机科学家和程序员几十年来一直在做的事情。这种方法久经考验，屡次被证明是正确的。它是如此普遍，以至于它有自己的名字：动态规划。即使你以前从未听说过这个术语，也很有可能你已经使用过动态规划，或者已经对其核心概念有了一定的了解。
就我们的目的而言，在算法设计的背景下，动态规划的理解特别有用。在这个系列的课程中，我们已经处理了大量的算法，从排序算法，到遍历算法，到寻路算法。然而，我们还没有真正谈论过这些算法是如何_构建的。不用担心--今天所有这些都会改变。现在是时候让我们戴上设计师的帽子，深入研究使用动态规划原理设计算法的微妙复杂性了。
让我们开始吧!
算法设计的范式

动态规划（缩写为 &#34;DP&#34;）这个术语有一个名声，那就是听起来比它的实际情况更令人生畏。我认为这在很大程度上与它的名字有关，至少对我来说，它听起来非常复杂。但我们稍后再来讨论这个名字。让我们从一个定义开始，以试图让我们明白 &#34;动态规划 &#34;到底是什么意思。
思考动态规划的一个有用的方法是记住它总是与优化联系在一起，也就是一个算法在任何时候都应该选择最好结果，不管它是在排序、搜索、遍历一个结构，还是寻找一个路径。因为动态规划植根于优化，这个术语可以与动态优化这个术语互换。

动态编程定义
但是，动态编程或动态优化究竟是如何与优化算法联系起来的呢？换句话说，这种形式的算法设计对优化算法有什么作用？
好吧，说到底，一个动态编程算通过将一个复杂的问题分解成更小的部分来解决它。在一个DP算法将一个问题分解成更小的部分后，它在计算一次后将结果存储到这些子问题中。
这个定义一开始可能听起来非常模糊不清，但我保证，如果我们把它与其他算法设计范式相比较，它就会变得更有意义了
分治算法

有两种设计算法的方法，我们已经在这个系列中看到了。其中一种我们知道它的名字：分治。我们早在第一次介绍合并排序算法时就了解了划分与解决。我们会记得，划分与解决算法将一个问题划分为更简单的版本，然后将它在较小的子问题上使用的解决方案应用于较大的问题本身。如果我们回想一下，当我们学习合并排序时，我们会记得该算法是如何合并其子问题的答案并使用递归将元素合并在一起，同时对它们进行排序。这也是dc算法的一个特点。
但我们对算法设计的了解并不仅仅止于分治的方法。上周，我们学习了Dijkstra算法，它在搜索两个顶点之间的最佳最短路径时，选择了要访问的最佳顶点。事实证明，Dijkstra算法是一个不同算法设计范式的例子--贪婪算法。
贪婪算法

像Dijkstra算法这样的算法被认为是贪婪算法，因为它们会选择当下可能的最佳选项，这通常被称为 &#34;贪婪选择&#34;。贪婪算法在局部水平上做出最优选择--也就是说，在每个阶段做出最有效的选择，乐观地希望，如果他们在每个点上选择最好的选项，最终，他们将到达 &#34;全局最优选择&#34;。

贪婪算法在当下做出最佳选择，然后解决他们做出的选择所产生的任何子问题。作为一个算法，做出 &#34;贪婪选择 &#34;的一个后果是，该算法选择了它能选择的最好的选项，并且永远不会回头去重新考虑它的选择。最终，这意味着一个贪婪的算法很可能会找到一个实际上不是最理想的选择的解决方案！这就是Dijkstra算法。

Dijkstra算法是贪婪算法的一个典型例子，因为它根据每一步存储的结果来选择下一个要访问的顶点。我们可以回顾一下上周对Dijkstra算法的深入研究，该算法根据每个顶点的边缘权重，看哪个顶点的路径是目前已知的最短路径，然后下一步访问该顶点。

动态编程：一个定义
Dijkstra的算法从来没有搜索过_所有_的路径。它的搜索并不详尽；一旦做出选择，它就不会重新考虑，这意味着它不会搜索它选择不访问的所有顶点的 &#34;子问题&#34;。这有时会产生问题，因为如果算法在早期阶段找到一个具有最短路径的顶点，然后继续走访其邻居，那么它很可能找不到全局最优化的路径。

好吧，我们有分治算法，也有贪婪算法。但是，让我们回到手头的问题上：了解动态编程算法与这两种算法的比较情况
如果我们将这三种形式的算法设计相互比较，我们就会开始看到DP算法和它的两个对应方之间有一些明显的相似之处（也有一些明显的不同）。
看看上面的表格，我们可以看到DP算法在一个明显的方面与分治相似：它们都涉及将一个大问题分解成更小、更简单的子问题。

然而，我们也会看到动态编程方法和分而治之方法之间的一个主要区别。在DP范式中，当我们将大问题分解成小部分时，这些子问题实际上是重叠的。这是另一种思考方式：动态编程算法中的子问题是反复出现的，而且会重复出现。在DP方法中，大问题是通过解决和记忆重叠的子问题来解决的。相比之下，重叠的子问题并不是分而治之方法的要求。那么，动态编程与贪婪算法范式相比如何？但是，动态编程或动态优化究竟是如何与优化算法联系起来的呢？换句话说，这种形式的算法设计对优化算法有什么作用？

动态编程与贪婪算法范式相比。
好吧，首先，这两种方法都必须在两个各自的算法运行的每个阶段做出选择（最好是最优选择）。这通常被称为使用最优子结构，指的是算法找到的最优解，通过代理，包含其内部每个子问题的最佳解。
然而，这两种范式以截然不同的方式处理 &#34;尽可能做出最佳选择 &#34;的问题。
正如我们已经了解到的，贪婪算法做出一个初始的贪婪选择，然后在每个阶段继续做出最佳选择，使自己只解决更大、更复杂问题中的一个子问题。动态编程是非常不同的；DP范式为每一个子问题找到最佳解决方案，并从所有的子问题中选择最佳方案。
用一种更简单的方式来思考动态编程算法与贪婪算法的比较是这样的。

动态编程算法将详尽地搜索所有可能的子问题，然后在此基础上选择最佳解决方案。贪婪算法只搜索一个子问题，这意味着根据定义，它们是不太详尽的搜索。

这给我们带来了一个重要的问题：动态编程算法究竟是如何进行如此广泛的搜索工作的？DP算法究竟是如何跟踪所有重叠的子问题的？
现在是我们研究的时候了。
Remember to remember

我们已经知道，动态编程类似于分而治之，因为它涉及到子问题，并将事物分解成更容易计算的部分。但是，我们也知道，DP算法可以计算出现的每一个重叠的子问题--换句话说，如果存在许多子问题，它可以计算所有的子问题，然后从其中挑选出最好的一个作为最终的解决方案。

计算各种子问题的所有解决方案（然后选择最好的一个）的诀窍是_记住以前的解决方案_。

让我们用一个简单的例子来说明我的意思。想象一下，我们必须解决 &#34;5+5+5+5 &#34;的问题。我们将如何解决这个问题？嗯，我们只是把它们加起来，对吗？我们知道 &#34;5+5+5+5=20&#34;。完成了。
但是，如果我们在最后再加上一个5呢？5 + 5 + 5 + 5 + 5 = ?. 在心理上，我们会怎么做？我们会不会把每个5加起来，一个接一个，一遍又一遍？

如何思考动态编程！？
不可能! 我们可能只是在想，&#34;哦，我刚刚做了那个数学题。我知道之前是20，现在又多了一个5，所以答案一定是25！&#34;我们记住了之前解决的问题的解决方案，当我们不得不解决一个以它为基础的问题时，又使用了它。
动态编程所做的事情与我们刚才在那个简单的数学问题上所做的事情类似。它记得它以前见过并解决过的子问题。当它再次看到相同的子问题时--这就是我们所说的重叠子问题,它知道它不需要多次重新计算工作。它只是从它以前算出的解决方案中提取!

动态编程使我们能够避免重复自己。
动态编程的魅力在于，它可以让我们避免重复自己，从而避免通过记住沿途已经解决的问题的部分内容而重复一些工作。不重复自己的能力听起来很好，但看到它在行动中确实有帮助。有一个著名的例子被反复用来说明DP算法是多么强大，我们接下来要看的就是这个例子。好消息是，我们已经熟悉了这个著名的例子：它就是我们亲爱的老朋友，斐波那契数列!
我们会记得，斐波那契数列与黄金分割率密切相关，是以 &#34;0 &#34;和 &#34;1 &#34;开头的数列。为了推导出斐波那契数列中的任何数字，我们需要找到该数字之前的两个数字并将其相加。

返回解决斐波那契问题
例如，要找到 &#34;0、1、2、3、5 &#34;之后的数字，我们将 &#34;3+5 &#34;相加，并知道下一个数字是 &#34;8&#34;。在斐波那契数列中寻找一个数字的公式的一个更抽象的定义方式是。F[n]=F[n-1]+F[n-2]，其中n代表斐波那契数组中的索引。根据这个公式，我们也知道斐波那契可以递归求解，因为我们不可避免地会发现，如果我们还不知道斐波那契数列中的前一个数字，就需要使用递归来找到它。
然而，看看上面说明的价值的递归 &#34;树&#34;的例子，我们会注意到我们在重复自己。在递归求解斐波那契数F[6]，即第七个斐波那契数时，我们必须计算F[5]和F[4]。但是，为了计算 F[5]，我们又需要解决F[4]的问题。
下面是一个抽象出来的同样的递归重复问题的例子。

为什么我们要多次重新计算相同的数值？
在求解F[n]时，n是什么并不重要；如果我们使用递归，我们最终将不得不重新计算斐波那契数列的一部分，而且不止一次。例如，在上面的树中，我们正在计算F[n-3]两次，而且我们也在计算F[n-2]两次。这看起来效率很低，我们应该可以做得更好。
好消息是：我们可以当然是使用动态编程。
我们知道，动态编程可以让我们记住我们以前见过并解决过的问题的解决方案。斐波那契的例子就是一个很好的例子，我们想记住我们已经解决过的斐波那契数的解决方案。DP算法如何记住它已经解决过的问题的方法被称为memoization。

用记忆化来记住我们已经解决的问题!
记忆化很像在便笺上做笔记：当我们遇到一个看起来很重要的问题时（即使它不重要），我们写下它的答案并记下来，记忆化它。就像前面的 &#34;5+5+5+5+5 &#34;问题一样，如果我们以后遇到同样的问题，我们就不需要再去做重新计算所有问题的心算了。我们已经解决了80%的问题，因为我们可以重复使用之前的解决方案，只需在它的基础上进行，这比从头开始解决要容易得多

Memoization允许我们只运行一次计算，然后在以后重复使用，而不必重新计算。

大多数递归算法可以很容易地被记忆化。
早些时候，在我们使用记忆化之前，我们需要一次又一次地计算多个子问题。然而，通过采用记忆化，我们可以消除整个不必要的工作部分。这里显示的插图就体现了这一点。
现在，当求解 &#34;F[n]&#34;时，我们首先计算 &#34;F[n-1]&#34;。作为递归计算 &#34;F[n-1]&#34;解决方案的一部分，我们最终会求出 &#34;F[n-2]&#34;和 &#34;F[n-3]&#34;。每当我们第一次求解它们时，我们都会_记忆它们的解。
接下来，我们需要解决计算F[n]的第二部分：F[n-2]。当我们去计算F[n-2]的值时，我们会在实际计算之前检查是否已经解出了它。当我们第二次看到它时，我们知道我们已经解出了它，而且我们知道我们已经有了它的值，因为我们在记忆它的解法时记住了它。
记忆化使我们能够消除这个递归斐波那契树的一半，仅仅是因为我们记住了我们已经看到的子问题的解决方案作为一项规则，递归算法，包括斐波那契算法，可以被做成动态编程算法，使用记忆化来提高优化和速度。
好了，现在我们知道动态编程算法是如何找到最好的、最优化的解决方案的：它们解决了所有潜在的子问题。我们也知道他们是如何解决所有的子问题的：他们记住了重叠的解决方案，并使用记忆化来避免不必要的计算。但是，使用记忆化的动态编程算法的效率有多高呢？
让我们通过观察空间和时间复杂性的问题来回答这个问题。
记忆化所有的东西

如果没有记忆化，解决斐波那契数列中第n个值的算法的运行时间复杂度是......不是那么优雅。
对于任何我们需要求解的指数为n的斐波那契数字，我们需要递归调用相同的斐波那契算法来求解n-1和n-2的值。我们已经知道其中一些数学知识。我们知道，如果两个量之间的比值与两个元素相加的比值相同，那么这两个量就有一个黄金比例。这两个内部算法的综合运行时间T(n-1)和时间T(n-2)最终相当于$\phi$ 提高到任何n的幂。

递归求解斐波那契的时间复杂度，没有记忆化。
还有一些恒定的时间O(1)，涉及到对数字进行求和并返回正确的值，但这可以忽略不计。重要的是--希望我们脑子里响起的响亮的红色警报--这里涉及到一个指数! 事实上，它导致了指数运行时间_，或O(2^n)！我们总是希望避免这种情况。

用记忆化解决斐波那契的时间复杂性。
好吧，如果没有记忆化，斐波那契的递归形式并不是太好。
但是有了记忆化之后呢？好吧，关于 &#34;记住的&#34;、记忆化的值的好处是，它们几乎不需要我们花费时间在我们可能存储的字典/哈希/数组中进行实际查找。换句话说，查找一个记忆化值的实际成本是O(1)，constant时间。
然而，当我们第一次遇到一个子问题时，我们仍然需要先解决它，然后才能将其记忆化化。对斐波那契算法的非记忆化调用将取决于n是什么。如果我们要找的是第10个元素，那么计算斐波那契数列所需的调用将比找第100个元素的调用要少很多。因此，对每个非记忆化元素第一次运行斐波那契算法的工作需要linear，O(n)时间。
与该算法的非记忆化录版本类似，这里也有一些恒定的时间O(1)，涉及到对数字进行求和并返回正确的值，但这可以忽略不计。这导致了O(n)+O(1)+O(1)的运行时间，这仍然相当于linear，O(n)的时间。
线性时间比指数时间要好得多! 对于一个小的动态编程算法来说，还不错，是吗？
那么，当涉及到空间问题时，Fibonacci的记忆化版本与非记忆化版本相比如何？

鉴于Fibonacci的记忆化录版本需要记住旧的子问题解决方案，DP范式为了节省时间而牺牲了一些空间。

这是使用动态编程方法的部分权衡，取决于我们需要解决多少个子问题，以及我们对用来存储这些子问题解决方案的数据结构有多聪明，牺牲空间换取时间往往是可取的--特别是当我们知道我们需要查询许多斐波那契的值，并且知道我们以后会一再重复使用我们的旧解决方案。

动态编程的两种方法。
动态编程范式的强大不仅在于其效率，还在于其运行时的复杂性。然而，值得一提的是，有两种主要的动态编程算法方法；我们在这篇文章中只学习一种，但重要的是要对这两种方法的识别的能力和使并运用自如。
自上而下的动态编程范式是我们在斐波那契实验中使用的范式。在自上而下的方法中，我们从大型的、复杂的问题开始，并了解如何将其分解为较小的子问题，将问题记忆化为若干部分。
与此相反的是自下而上的动态编程方法，它从最小的子问题开始，找出它们的解决方案，然后慢慢建立自己，以解决更大、更复杂的子问题。
在解决Fibonacci的案例中，自下而上的技术将涉及我们解决Fibonacci中的第一个元素，然后向上建立我们的方式，最终到达我们试图确定的任何n值的解决方案。我们仍然会使用记忆化来帮助我们存储数值--我们只是从 &#34;另一端 &#34;来解决问题。当我们第一次了解斐波那契时，自下而上的方法可能是我们大多数人更喜欢的方法。如果我们想一想，我们都是从0开始数斐波那契，然后是1，然后是2，直到我们数到我们要找的数字。
自下而上的动态编程算法有一个很大的好处，那就是：我们只需要把最后两个值记下来。因为我们知道，我们是在往上走，而不是从上往下走--我们不需要去存储之前的所有数值。我们真正关心的只是最后两个，直到我们到达 &#34;n&#34;的值。这使得我们不需要一个更大的数据结构来占用记忆值的空间。相反，我们可以只对前两个值进行记忆化，这使我们可以实现constant，或O(1)空间。
动态编程，即使有其所有的特异性，一旦我们将其分解为移动的部分，也不是那么令人生厌了。

理查德-贝尔曼
我在前面提到，&#34;动态编程 &#34;这个名字让人感觉比实际情况更令人生畏。在DP的名字背后有一个有趣的事实：它其实并不那么复杂。
动态编程是由Richard Bellman在20世纪40年代发明的，他是一位计算机科学家，当时在一家名为RAND的公司从事数学研究。事实证明，兰德公司受雇于美国空军，这意味着他们经常要向国防部长报告，而国防部长的名字是查尔斯-埃尔文-威尔逊。
在贝尔曼的自传《飓风之眼》（_Eye of the Hurricane: 自传中，他解释了他是如何想出这个算法设计范式的名字的。

[威尔逊]实际上对研究这个词有一种病态的恐惧和憎恶。我不是轻率地使用这个词；我是准确地使用它。如果人们在他面前使用研究这个词，他的脸就会发红，他会变得很暴躁......因此，我觉得我必须做些什么来掩盖威尔逊和空军的事实，即我确实是在兰德公司里做数学。我可以选择什么头衔，什么名字？首先，我对规划、决策和思考感兴趣。但由于各种原因，规划不是一个好词。因此，我决定使用 &#34;编程 &#34;这个词。我想表达的是，这是动态的，这是多阶段的，这是时间变化的。我想，让我们一石二鸟。让我们使用一个具有绝对精确含义的词，即经典物理意义上的动态。作为一个形容词，它还有一个非常有趣的特性，就是不可能在贬义上使用动态这个词。试着想出一些可能会给它带来贬义的组合。这是不可能的。因此，我认为动态编程是一个好名字。这是一个连议员都不会反对的东西。所以我把它作为我的活动的一个保护伞。

这个故事的寓意（如果有的话）是，有时候，名字吓人的东西实际上可能只是因为这个名字听起来不错而被命名。因此，在我看来，听起来吓人的东西没什么好怕的！只要确保不告诉就可以了
资源

动态编程是一个在计算机科学中经常以困难问题的形式出现的话题。一些计算机科学课程很早就介绍了它，然后就再也没有真正回过头来讨论这种形式的算法设计。然而，动态编程背后的理论却一再出现，通常是以最复杂的形式出现--有时甚至是无法解决的! - 的问题。如果你有兴趣了解更多，这里有一些很好的资源可以帮助你开始。

		自动登录	找回密码
密码			立即注册

什么是动态规划（Dynamic Programming）？动态规划的 ...

本帖子中包含更多资源