动态编程:示例,常见问题和解决方案

毫无疑问,动态编程问题在编程采访中会非常令人生畏。即使您可能知道需要使用动态编程方法解决问题,但要能够在有限的时间内提出可行的解决方案也是一个挑战。

擅长解决动态编程问题的最好方法是尽可能多地解决它们。尽管您不一定需要记住每个问题的解决方案,但最好是了解如何实施一个解决方案。

什么是动态编程?

简而言之,动态编程是递归算法的一种优化方法,其中大多数用于解决计算或数学问题。

您也可以将其称为解决最优化问题的算法技术,方法是将其分解为更简单的子问题。动态编程所基于的一个关键原则是,问题的最佳解决方案取决于其子问题的解决方案。

只要我们看到递归解决方案重复调用相同的输入,就可以使用动态编程对其进行优化。这个想法只是简单地存储子问题的结果,这样我们以后就不必在需要时重新计算它们。

动态编程的解决方案具有多项式复杂性,与其他技术(例如递归或回溯)相比,可确保更快的运行时间。在大多数情况下,动态编程可将时间复杂度(也称为big-O )从指数降低为多项式。

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

动态编程问题

1.背包问题

问题陈述

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

您将获得两个整数数组,分别是value [0..n-1]weights [0..n-1] ,它们分别表示与n个项目相关联的值和权重。还给出了代表背包容量的整数W。

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

算法

  • 创建一个具有n + 1行和w + 1列的二维数组。行号n表示从1到i的项目集,列号w表示袋子的最大承载能力。
  • [i] [j]处的数值表示最大重量为j的袋子中直到i的物品的总价值。
  • 在阵列中的每个坐标[i] [j],挑最大值,我们可以在不获得I,或者我们可以与项目i —取较大值获得的最大值。
  • 通过包括项目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的值初始化为等于该值。这表示组成该数量所需的最大硬币数量(使用面额为1的硬币)。
  • 由于没有0的面额,因此初始化array [0] = 0的基本情况。
  • 对于每个其他索引i ,我们将其中的值(最初设置为n + 1 )与值array [ik] +1进行比较,其中k小于i 。这实际上会检查直到i-1为止的整个数组,以找到我们可以使用的最小硬币数量。
  • 如果在任何数组[IK] + 1大于在阵列中的现有值较小[I]中,与所述一个在阵列[IK] 1阵列[I]替换的值。

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[jd[i]])
numbers[j] = minimum

return numbers[amount]

3.斐波那契

问题陈述

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

它由以下递归关系定义: 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 = 0n = 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并开始吧!