解决|关于动态规划,你想知道的都在这里了!


解决|关于动态规划,你想知道的都在这里了!
文章插图
作者 | Your DevOps Guy
翻译| 火火酱~,责编 | 晋兆雨
出品 | AI科技大本营
头图 | 付费下载于视觉中国
什么是动态规划?它又有什么重要的呢?
在本文中,我将介绍由Richard Bellman在20世纪50年代提出的动态规划(dynamic programming)概念,这是一种强大的算法设计技术——将问题分解成多个小问题,存储它们的解,通过将其结合在一起,最终得到原始问题的解决方案。
FAANG编程面试中最难的问题通常都属于这一类。你在面试的过程中也很可能会被要求解决这样的问题,因此,了解这项技术的重要性自然不言而喻。接下来,我将解释什么是动态规划,给出一个解决动态规划问题的秘诀,并且和大家一起分析几个示例,以便你能够更好地理解其应用场合和应用方法。
和我以往有关编程面试的文章一样,在本文中,我将分享自己在使用这种方法解决问题时的思考过程,这样当你在面对其中一个问题时,按照这个过程一定也能解决。不需要死记硬背,我们只需要通过了解技术和实践,将想法转化成代码技能。编程的重点不在于学习编程语言,而在于分析问题,考虑不同的解决方案,从中选出最优解,然后通过某种编程语言将其转化为现实。
动态规划
动态规划是一种解决最优化、搜索和计数问题的通用技术,这些问题都可以被分解为多个子问题。要应用动态规划,问题就必须具备以下两个属性:
最优子结构(Optimal substructure)
重叠子问题(Overlapping subproblems)
(1)最优子结构
如果大小为n的问题的最优解可以由大小小于n的问题的同一实例的最优解推导出,则该问题具有最优子结构。
例如,如果从巴黎到莫斯科的最短路径会经过柏林,那么可以由巴黎到柏林的最短路径和柏林到莫斯科的最短路径组成。
如果一个问题可以通过组合非重叠子问题的最优解来解决,这种策略被称为分治法。这就是归并排序和快速排序不属于动态规划问题的原因。
(2)重叠子问题
举一个大家都很熟悉的例子,斐波那契数列,即从第三项开始,每一项都等于前两项之和。斐波那契数列可以表示为
大家都说一张图片胜过千言万语,所以......(摘自《Elements of programming interviews》)
解决|关于动态规划,你想知道的都在这里了!
文章插图
要想解出F(n),就需要解出F(n-1)和F(n-2),但是F(n-1)又需要F(n-2)和F(n-3)。这样一来,F(n-2)是重复的,来自于同一个问题的两个不同实例——计算一个斐波那契数。
这可以用一个递归函数来表示:
要想解决一个大小为n的问题,我们可以调用相同的函数来解决同一问题的一个实例,但实例规模比原始问题规模小一些。
我们一直不断地调用该函数,直到到达基础用例,也就是停止条件,在此处即n = 0或n = 1。
这就引出了递归和动态规划之间的关系。
递归和动态规划
从概念上讲,动态规划涉及到递归问题。我们希望通过同一个问题的较小实例来解决原始问题,而递归是在代码中实现这一点的最佳选择。与纯递归函数的不同之处在于,我们将用空间来换取时间:我们将存储各子问题的最优解,进而高效地找到原始问题的最优解。
当然,这并不是说我们都必须使用递归来解决动态规划问题。还可以通过一种迭代方法来编写动态规划解决方案。
自下而上的动态规划
我们需要将所有子问题的解决方案填入表格(从基本用例开始),并用它来构建我们正在寻找的解决方案。这个过程是通过迭代的方式完成的,你可以从下面列别中任选其一作为存储子问题解决方案的数据结构:
多维(以及一维)数组——最常用的方法;
哈希表;
二叉搜索树;
自上而下的动态规划
编写递归算法并添加缓存层,以避免重复的函数调用。
或许现在看起来有点糊涂,但等一会儿讲到示例后,一切都会清楚得多。
如何解决动态规划问题
如果一个问题想要通过动态规划来解决的话,就必须具备最优子结构和重叠子问题这两个属性。当直觉告诉你动态规划或许是一个可行的解决方案时,你需要验证其是否具备这两个属性。
下面让我们试着感受一下,什么样的问题可以用动态规划来解决。一切以“找到”开头的问题:
... ...的前n个元素;
... ...的所有方式;
有多少种... ...方式;
第n个... ... ;
... ...的最优解决方案;