毫无疑问，动态规划问题在编码面试中可能会非常可怕。即使你知道一个问题需要用动态规划方法来解决，在有限的时间内想出一个可行的解决方案也是一个挑战。

精通动态规划问题的最好方法是尽可能多地研究它们。虽然你不一定要记住每个问题的解决方案，但有一个如何着手实施的想法是很好的。

什么是动态规划(dynamic programming)？

简单地说，动态规划是递归算法的一种优化方法，大多数递归算法用于解决计算或数学问题。

你也可以称之为一种算法技术，通过将优化问题分解成更简单的子问题来解决。动态规划的一个关键原则是，问题的最优解取决于子问题的解。

每当我们看到一个递归解决方案对相同的输入重复调用时，我们就可以使用动态规划来优化它。其思想是简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。

动态编程的解决方案具有多项式复杂性，这确保了比递归或回溯等其他技术更快的运行时间。在大多数情况下，动态规划减少了时间复杂性，也被称为大O，从指数到多项式。

现在您已经对什么是动态规划有了一个很好的了解，是时候检查一些常见的问题及其解决方案了。

动态规划问题

1背包问题

问题陈述

给定一组项目，每个项目都有一个权重和一个值，确定要包含在集合中的每个项目的数量，以便总权重不超过给定的限制，并且总值尽可能大。

我们为您提供了两个整数数组值[0..n-1]和权重[0..n-1]，它们分别表示与n个项相关联的值和权重。同时给出了一个表示背包容量的整数W。

这里我们要解决0/1背包问题，这意味着我们可以选择添加或排除一个项目。

算法

• 创建一个包含n+1行和w+1列的二维数组。行号n表示从1到i的一组项目，列号w表示行李的最大承载能力。
• [i][j]处的数值表示一个可携带最大重量j的袋子中直到i为止的物品的总价值。
• 在数组中的每个坐标[i][j]处，选取不带i项的最大值，或带i项的最大值，以较大者为准。
• 包括第一项所能获得的最大值是第一项本身和背包剩余容量所能获得的最大值之和。
• 执行此步骤，直到找到第w行的最大值。

代码

def FindMax(W, n, values, weights): MaxVals = [[0 for x in range(W + 1)] for x in range(n + 1)] for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: MaxVals[i][w] = 0 elif weights[i-1] <= w: MaxVals[i][w] = max(values[i-1] + MaxVals[i-1][w-weights[i-1]], MaxVals[i-1][w]) else: MaxVals[i][w] = MaxVals[i-1][w] return MaxVals[n][W]

2硬币兑换问题

问题陈述

假设给你一个数字数组，代表每枚硬币的价值。给定一个特定的数量，找出**这个数量所需的最小硬币数量。

算法

• 初始化大小为n+1的数组，其中n是数量。将数组中每个索引i的值初始化为等于amount。这表示组成该金额所需的最大硬币数量（使用面额为1的硬币）。
• 因为0没有命名，所以初始化数组[0]=0的基本情况。
• 对于每个其他索引i，我们将其中的值（最初设置为n+1）与值数组[i-k]+1进行比较，其中k小于i。这基本上检查整个数组直到i-1，以找到我们可以使用的最小可能硬币数。
• 如果任何数组[i-k]+1处的值小于数组[i]处的现有值，则将数组[i]处的值替换为数组[i-k]+1处的值。

代码

def coin_change(d, amount, k): numbers = [0]*(amount+1) for j in range(1, amount+1): minimum = amount for i in range(1, k+1): if(j >= d[i]): minimum = min(minimum, 1 + numbers[j-d[i]]) numbers[j] = minimum return numbers[amount]

三。斐波那契

问题陈述

斐波那契级数是一个整数序列，其中级数中的下一个整数是前两个整数的和。

它由以下递归关系定义：F（0）=0，F（n）=F（n-1）+F（n-2），其中F（n）是第n项。在这个问题中，我们必须生成斐波那契数列中的所有数字，直到给定的第n项。

算法

• 首先，使用递归方法实现给定的递归关系。
• 递归地解决这个问题需要将F（n）分解为F（n-1）+F（n-2），然后用F（n-1）和F（n+2）作为参数调用函数。我们这样做，直到达到n=0或n=1的基本情况。
• 现在，我们使用一种叫做记忆的技术。将所有函数调用的结果存储在一个数组中。这将确保每n，F（n）只需计算一次。
• 对于任何后续的计算，它的值可以简单地从数组中以恒定的时间获取。

代码

def fibonacci(n): fibNums = [0, 1] for i in range(2, n+1): fibNums.append(fibNums[i-1] + fibNums[i-2]) return fibNums[n]

4子序列

问题陈述

求给定数组中最长递增子序列的长度。最长递增子序列是一个递增顺序的数字数组中的子序列。子序列中的数字必须是唯一的并按升序排列。

此外，序列的项目不需要是连续的。

算法

• 从递归方法开始，计算从索引0到索引i的每个可能子数组的最长递增子序列的值，其中i小于或等于数组的大小。
• 要将此方法转换为动态方法，请创建一个数组来存储每个子序列的值。将此数组的所有值初始化为0。
• 该数组的每个索引i对应于大小为i的子数组的最长递增子序列的长度。
• 现在，对于findLIS的每个递归调用（arr，n），检查数组的第n个索引。如果该值为0，则使用第一步中的方法计算该值，并将其存储在第n个索引中。
• 最后，从数组返回最大值。这是给定大小n的最长递增子序列的长度。

代码

def findLIS(myArray): n = len(myArray) lis = [0]*n for i in range (1 , n): for j in range(0 , i): if myArray[i] > myArray[j] and lis[i]< lis[j] + 1 : lis[i] = lis[j]+1 maxVal= 0 for i in range(n): maxVal = max(maxVal , lis[i]) return maxVal

动态规划问题的解法

现在您已经学习了一些最流行的动态编程问题，现在是时候自己尝试实现这些解决方案了。如果你被困住了，你可以随时回来，并参考上述每个问题的算法部分。

考虑到递归和动态编程等技术如今是多么流行，不妨看看一些流行的平台，在那里您可以学习这些概念并磨练您的编码技能。虽然你可能不会每天遇到这些问题，但你肯定会在技术面试中遇到它们。

当然，当你去参加下一次面试时，掌握一些常见问题的诀窍肯定会有好处。所以打开你最喜欢的IDE，开始吧！