解决|关于动态规划，你想知道的都在这里了！实例|于同|最短路径|子结构

文章插图
作者 | 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个... ... ；
... ...的最优解决方案；