综合规划最新消息（你想知道的都在这里了）(1)

综合规划最新消息（你想知道的都在这里了）(2)

作者 | Your DevOps Guy

翻译| 火火酱~，责编 | 晋兆雨

出品 | AI科技大本营

头图 | 付费下载于视觉中国

综合规划最新消息（你想知道的都在这里了）(3)

什么是动态规划？它又有什么重要的呢？

在本文中，我将介绍由Richard Bellman在20世纪50年代提出的动态规划（dynamic programming）概念，这是一种强大的算法设计技术——将问题分解成多个小问题，存储它们的解，通过将其结合在一起，最终得到原始问题的解决方案。

FAANG编程面试中最难的问题通常都属于这一类。你在面试的过程中也很可能会被要求解决这样的问题，因此，了解这项技术的重要性自然不言而喻。接下来，我将解释什么是动态规划，给出一个解决动态规划问题的秘诀，并且和大家一起分析几个示例，以便你能够更好地理解其应用场合和应用方法。

和我以往有关编程面试的文章一样，在本文中，我将分享自己在使用这种方法解决问题时的思考过程，这样当你在面对其中一个问题时，按照这个过程一定也能解决。不需要死记硬背，我们只需要通过了解技术和实践，将想法转化成代码技能。编程的重点不在于学习编程语言，而在于分析问题，考虑不同的解决方案，从中选出最优解，然后通过某种编程语言将其转化为现实。

动态规划

动态规划是一种解决最优化、搜索和计数问题的通用技术，这些问题都可以被分解为多个子问题。要应用动态规划，问题就必须具备以下两个属性：

（1）最优子结构

如果大小为n的问题的最优解可以由大小小于n的问题的同一实例的最优解推导出，则该问题具有最优子结构。

例如，如果从巴黎到莫斯科的最短路径会经过柏林，那么可以由巴黎到柏林的最短路径和柏林到莫斯科的最短路径组成。

如果一个问题可以通过组合非重叠子问题的最优解来解决，这种策略被称为分治法。这就是归并排序和快速排序不属于动态规划问题的原因。

（2）重叠子问题

举一个大家都很熟悉的例子，斐波那契数列，即从第三项开始，每一项都等于前两项之和。斐波那契数列可以表示为

F(0) = F(1) = 1F(n) = F(n-1) F(n-2)

大家都说一张图片胜过千言万语，所以......（摘自《Elements of programming interviews》）

综合规划最新消息（你想知道的都在这里了）(4)

要想解出F（n），就需要解出F（n-1）和F（n-2），但是F（n-1）又需要F（n-2）和F（n-3）。这样一来，F（n-2）是重复的，来自于同一个问题的两个不同实例——计算一个斐波那契数。

这可以用一个递归函数来表示：

这就引出了递归和动态规划之间的关系。

递归和动态规划

从概念上讲，动态规划涉及到递归问题。我们希望通过同一个问题的较小实例来解决原始问题，而递归是在代码中实现这一点的最佳选择。与纯递归函数的不同之处在于，我们将用空间来换取时间：我们将存储各子问题的最优解，进而高效地找到原始问题的最优解。

当然，这并不是说我们都必须使用递归来解决动态规划问题。还可以通过一种迭代方法来编写动态规划解决方案。

自下而上的动态规划

我们需要将所有子问题的解决方案填入表格（从基本用例开始），并用它来构建我们正在寻找的解决方案。这个过程是通过迭代的方式完成的，你可以从下面列别中任选其一作为存储子问题解决方案的数据结构：

自上而下的动态规划

编写递归算法并添加缓存层，以避免重复的函数调用。

或许现在看起来有点糊涂，但等一会儿讲到示例后，一切都会清楚得多。

如何解决动态规划问题

如果一个问题想要通过动态规划来解决的话，就必须具备最优子结构和重叠子问题这两个属性。当直觉告诉你动态规划或许是一个可行的解决方案时，你需要验证其是否具备这两个属性。

下面让我们试着感受一下，什么样的问题可以用动态规划来解决。一切以“找到”开头的问题：

都是潜在“候选人”。

解决动态规划问题的步骤

很不幸，解决动态规划问题并没有什么通用秘诀。我们需要在经历过很多问题之后，才能逐渐掌握其诀窍。这确实不容易，毕竟这可能会是你在面试中遇到的最难的问题了。但也先不要气馁，简单来讲，就是用相对简单的工具针对问题进行建模，并不需要花哨的数据结构或算法。

我已经解决过很多此类问题了，但有时还是会觉得毫无头绪，找不到解决方法。练习得越多，就越容易。以下这几点或许能带你走近解决动态规划问题的秘诀：

复杂度分析因问题而异，但一般来说，时间复杂度可以表示为：

时间~子问题个数*每个子问题的时间

计算自下而上解决方案的空间复杂度很简单，因为其等于存储子问题解决方案所需的空间（多维数组）。

示例

我已经根据所涉及的独立维度的数量对问题进行了分类。这一步并不是必须的，但我发现在设计解决方案时，遵循一定的心理模型是非常有用的。随着编写的代码越来越多，你会找到一些模式，而这就是其中之一。不妨试一下，如果觉得有用的话就用起来吧。

一维问题

（1）斐波那契

因为现在大家都已经对这个问题非常熟悉了，所以我就直接给出递归解决方案：

int fib(int n) {if (n == 0 || n == 1)return 1;elsereturn fib(n - 1) fib(n - 2);}}

从递归到自上而下的过程通常都有固定的模式：

int fib(int n) {vector<int> cache(n 1, -1);return fib_helper(n, cache);}intfib_helper(int n, vector<int> &cache) {if(-1 != cache[n])return cache[n];if (n == 0 || n == 1)cache[n] = 1;elsecache[n] = fib_helper(n - 1, cache) fib_helper(n - 2, cache);return cache[n];}

这里，用到自下而上的解决方案，我们通过构建一个表（从基本用例为起点），来形成要找的问题的解决方案。这个表是一个一维数组：我们只需要存储较小的问题的解，就可以推导出原始问题的解。

int fib(int n) {vector<int> f(n 1, 0);f[1] = 1;for(int i = 2; i <= n; i )f[i] = f[i - 1] f[i - 2];return f[n];}

额外空间优化

这种方法可以进一步优化内存，但并不会优化时间（也可以通过其他技术更快地计算斐波纳契数列，但这就是另一篇文章的内容了），只需要使用3个变量，而不必使用数组，因为我们只需要跟踪两个值，即f （n - 1）和f （n - 2），就可以得到我们想要的输出——f （n）。

int fib(int n) {if (n == 0 || n == 1)return 1;//Variables that represent f(n - 1), f(n - 2) and f(n)int n1= 1, n2 = 1, f = 0;for (int i = 2; i <= n; i ) {f= n1 n2;n2 = n1;n1 = f;}return f;}

这种方法更高级，也更常见。如果只需要跟踪：

通过降维，我们提高了空间的复杂度。现在，你不必记住所有的细节，但在进行过一些实践之后，要试着自己提出这些优化方案，从而增强自己分析问题并将想法转化为代码的能力。在面试中，我会选择更简单的版本，只讨论潜在的优化方案。只有在编写了自己的“标准化”动态规划解决方案，并且时间充足的时候，才动手实施这些优化。

（2）爬楼梯

假设你正在爬一段有n个台阶的楼梯，每次可以爬1或2个台阶。那么要想爬到顶端的话，一共有多少种不同的方法呢？

例1:

例2:

解决方案

先试着自己解决一下这个问题。你可能会想到一个递归解决方案。回顾一下我的说明和前面的示例，看看是否可以自行编写出自上而下的的解决方案。

提示一下：既然这个问题以“有多少种方式”开头，那就应该能想到采用动态规划的潜在可能性。

在这种情况下，如果想要到达第N阶，就要经过第N-1阶或第N-2阶，因为一次可以爬1阶或2阶。如果我们能解决这两个子问题的话，就可以找到一般问题的解。我们将f（N）称为到第N阶的方法数。

不需要继续罗列下去了吧，你应该已经发现了：

这表示我们可以通过动态规划来求解该问题。

因为我已经在上一个例子中写过代码了，所以这里就不再写代码了。

大家可以在下方链接中试着编写并测试一下自己的解决方案。

（链接地址：https://leetcode.com/problems/climbing-stairs/?ref=hackernoon.com）

（3）最长递增子序列

给定一个未排序的整数数组，求最长递增子序列的长度。

例如，对于数组[10,9,2,5,3,7,101,18]而言，其输出为4，即序列[2,3,7,101]

解决方案

我们需要找到大小为n的数组的最长递增子序列的长度。这听起来像是一个可以通过动态规划来解决的优化问题，那么让我们来试一下。假设我们已经有了大小为N的问题的解，称其为s（n）,然后我们在数组中增加了一个额外元素，称为Y。那么，你能重复使用X的解决方案来解决这个新问题么？这个问题通常会为我们带来一些启发。

在这里，我们需要知道新元素是否可以扩展任一现有序列：

我们似乎得到了某种算法。继续我们的分析：

以下是该自下而上解决方案的代码。

int lengthOfLIS(const vector<int>& nums) {if(nums.empty)return 0;vector<int> dp(nums.size, 1);int maxSol = 1;for(int i = 0; i < nums.size; i){for(int j = 0; j < i; j){if(nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] 1);}}maxSol = max(maxSol, dp[i]);}return maxSol;}

大家可以在下方链接中试着编写并测试一下自己的解决方案。

（链接地址：https://leetcode.com/problems/longest-increasing-subsequence/?ref=hackernoon.com）

（4）有多少BST

对于给定的n，有多少结构唯一的存储值为1... ...n的BST（二叉搜索树）？

例子：

解决方案

我们一起来看看这个例子。假设我们有数字1、2、3、4、5，如何定义BST？

我只需要选择其中一个数作为根，先假设其为数字3，则：

我们可以解决（1，2）和（4，5）的相同子问题（暂且称其为解决方案L和R），数一数以3为根可以形成多少个BST，即L*R。如果我们对每一个可能的根都这样做，并且把所有的结果相加的话，就可以得到我们所需的解决方案C（n）。如你所见，有条不紊地从几个例子出发，可以帮助我们更好地设计算法。

其实，我们只需要：

实际上，我们并不关心数组两边的数字是什么。我们只需要子树的大小，即根的左右两边的元素个数。这个问题中的每个实例都会产生相同的结果。在之前的例子中，L和R都是C（2）的解。我们只需要计算一次C（2），缓存，然后重复使用即可。

int numTrees(int n) {vector<int> dp(n 1, 0);dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i){for(int j = 0; j < i; j){dp[i] = dp[j] * dp[i - 1 - j];}}return dp.back;}

大家可以在下方链接中试着编写并测试一下自己的解决方案。

（链接地址：https://leetcode.com/problems/unique-binary-search-trees/?ref=hackernoon.com）

二维问题

这些问题通常比较难建模，因为它涉及两个维度。常见的例子是，在两个字符串中迭代，或移动映射。

我曾在另一篇文章中说过，学习是迭代的。首先，要把注意力集中在理解基础知识上，然后再一点一点地增加更多的细节。

（1）最小路径和

给定m×n的非负数网格，找出一条从左上到右下的路径，使路径上所有数字之和最小。

注意：你只能选择向下移动或向右移动。

例子：

解决方案

最小化问题应该会让你想到动态规划。进一步分析，路径可以经过任意单元格C（i，j）（即不在上边框或左边框），单元格A = （i-1, j）和B=（i，j-1）。由此，我们发现，有些问题需要进行多次计算。此外，我们如果知道A和B的最优解，就可以计算出当前单元格的最优解为min(sol (A)，sol(B)) 1，因为我们只能通过当前单元格来表示A或B，要想移动到当前单元格就需要多走一步。换句话说，这是一个最优子结构和重叠问题。我们可以使用动态规划。

下面是由下而上的解决方案。

int minPathSum(const vector<vector<int>>& grid) {const int nrow = grid.size;if(nrow == 0)return 0;const int ncol = grid[0].size;vector<vector<int>> minSum(nrow, vector<int>(ncol, 0));minSum[0][0] = grid[0][0];for(int col = 1; col < ncol; col)minSum[0][col] = minSum[0][col - 1] grid[0][col];for(int row = 1; row < nrow; row)minSum[row][0] = minSum[row - 1][0] grid[row][0];for(int col = 1; col < ncol; col){for(int row = 1; row < nrow; row){minSum[row][col] = min(minSum[row - 1][col], minSum[row][col - 1]) grid[row][col];}}return minSum[nrow - 1][ncol - 1];}

边界条件定义在矩阵的边界上。只有一种方法可以获得边界上的点：从上一个点向右或向下移动一个格子。

大家可以在下方链接中试着编写并测试一下自己的解决方案。

（链接地址：https://leetcode.com/problems/minimum-path-sum/?ref=hackernoon.com）

（2）背包问题

给定两个整数数组val[0..n - 1]和wt [0 . .n-1]，分别表示与n个物品相关的值和权重。同时，给定一个代表背包容量的整数W，求val 的最大值子集，保证这个子集的权重之和小于或等于W。背包里的物品都必须保持完整，要么选择完整的物品，要么不选（0 - 1属性）。

解决方案

试着想出一个递归解决方案。在此基础上，添加一个缓存层，我们就会得到一个自上而下的动态规划解决方案了！

意思是，对于每一样物品，我们都有两个选择：

在试过所有组合之后，我们只选择最大值。这个过程极其缓慢，但却是迈向最终解决方案的第一步。

我们必须在两个选项之间做出决定（向集合中添加一个元素或跳过它），在许多问题中都面临这样的选择，所以我们一定要了解，并理解其应用场合和方式。

// Recursive. Try to turn this into a piece of top-down DP code.int knapSack(int W, int wt[], int val[], int n) {if (n == 0 || W == 0)return 0;if (wt[n - 1] > W)return knapSack(W, wt, val, n - 1);elsereturn max(val[n - 1] knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));}

以下是由下而上的解决方案：

// C style, in case you are not familiar with C vectorsint knapSack(int W, int wt[], int val[], int n) {int i, w;int K[n 1][W 1];for (i = 0; i <= n; i ) {for (w = 0; w <= W; w ) {if (i == 0 || w == 0)K[i][w] = 0;else if (wt[i - 1] <= w)K[i][w] = max( val[i - 1] K[i - 1][w - wt[i - 1]], K[i - 1][w]);elseK[i][w] = K[i - 1][w];}}return K[n][W];}

（3）最长公共子序列

给定两个字符串text 1和text 2，返回它们最长公共子序列的长度。

字符串的子序列是在不改变其余字符相对顺序的情况下，从原字符串中删除一些字符（也可以不删除）后生成的新字符串，例如，“ace”是“abcde”的子序列，但“aec”不是。两个字符串共同的子序列就被称为其公共子序列。

如果没有公共子序列的话，则返回0。

例子：

解决方案

同样，计算最长X的问题，动态规划应该可以帮得上忙。

鉴于大家已经有了一些动态规划的经验了，我就直接从示例中的两个属性说起。我们将字符串称为A和B，这个问题的解为f（A, B），解题思路是看最后两个字符是否相等：

虽然用例子来证明理论并不是开始数学证明的好方法，但是对于应付编程面试来说已经绰绰有余了。

int longestCommonSubsequence(const string &text1, const string &text2) {const int n = text1.length;const int m = text2.length;vector<vector<int>> dp(n 1, vector<int>(m 1,0));for(int i = 1; i <= n; i ){for(int j = 1; j <= m; j ){if(text1[i-1] == text2[j-1])dp[i][j] = dp[i-1][j-1] 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[n][m];}

大家可以在下方链接中试着编写并测试一下自己的解决方案。

（链接地址：https://leetcode.com/problems/longest-common-subsequence/?ref=hackernoon.com）

综合规划最新消息（你想知道的都在这里了）(5)

总结

我们一定要了解这些问题，因为很多其他问题都只是在此基础上的变种而已，但是不要死记硬背。主动去了解动态规划的使用场景和应用方式，并坚持练习，直到可以轻松地将自己的想法转换成代码。如你所见，这是需要讲究方法的。我们不一定要用到高级的算法或数据结构知识才能解决问题，数组就足够了。

我没有完成时间/空间复杂度分析，大家可以把它作为课后练习。欢迎大家随时在评论中留言，提出问题或分享观点。

原文链接：

https://hackernoon.com/all-you-need-to-know-about-dynamic-programming-0tj3e5l

本文由AI科技大本营翻译，转载请注明出处

综合规划最新消息（你想知道的都在这里了）(6)

,