动态规划(DP)问题是常见的面试问题，虽然这类问题在是否能有效评估某人在工程上的表现能力存疑，但是许多当红炸子鸡科技公司还是热衷于在面试中考察DP。如果候选人没有掌握解DP问题的套路，很可能在面试中遭遇滑铁卢！

解决动态规划(DP)问题的7个步骤

通过阅读本文，你可以判断问题是否为“DP 问题”并找出解决该方法。具体来说，需要执行以下7个步骤：

1. 如何识别DP问题
2. 识别问题变量
3. 清楚表达递归关系
4. 确定初始情况
5. 确定是要迭代实现还是递归实现
6. 添加备忘录
7. 确定时间复杂度

DP问题示例

这里介绍一个示例问题。在每个步骤的详细介绍部分，我都会提到这个问题，但是您也可以独立于问题阅读这些部分。

问题陈述：

 

疯狂的弹跳球游戏：在此问题中，我们处于疯狂的跳跃球上，试图停下来，同时要在行进过程避免沿途出现的尖峰。

规则如下：

1)您有一条平坦的跑道，但上面有一束尖刺。跑道由布尔数组表示，该布尔数组指示特定(离散)点是否有尖峰。清除了尖峰的则为True，没有清除的为False。

数组表示示例：

2)您获得的起始速度为S。S是任意给定点的非负整数，它表示您将在下一次跳跃时前进多少。

3)每次降落在地面上时，在下一次跳跃之前，您最多可以将速度调整1个单位。

4)您想要安全地在跑道上的任何地方停下来(不必在道路(数组)的尽头)。当速度变为0时，您会停下来。但是，如果您在任何时候落在尖峰上，疯狂的弹跳球都会爆裂，比赛结束，游戏失败！

函数的输出应为布尔值，指示我们是否可以在跑道上的某个地方安全地停止。

步骤1：如何识别动态编程问题

首先，我们要弄清楚DP本质上只是一种优化技术。 DP是一种解决问题的方法，它可以将问题分解为更简单的子问题的集合，仅解决一次这些子问题，然后存储其解决方案。下一次出现相同的子问题时，您无需重新计算其解决方案，只需查找先前计算出的解决方案即可。这节省了计算时间，但以(预期可接受的)适度的存储空间开销为代价。

认识到可以使用DP解决问题是解决问题的第一步，也是最困难的一步。您想问自己的问题是，您的问题解决方案是否可以表示为类似的较小问题的解决方案的函数。

在我们的示例问题中，给定跑道上的某个点，速度和前方的跑道情况，我们可以确定下一个可能跳下的位置。此外，似乎我们是否可以以当前速度从当前点停止，仅取决于我们是否可以从选择前往下一点的点停止。

这是一件很了不起的事情，因为通过向前发展，我们缩短了跑道，并使我们的问题更小。我们应该能够一直重复这一过程，直到我们可以停下来为止。

认识到动态编程问题通常是解决它的最困难的步骤。问题解决方案可以表达为类似较小问题的解决方案的函数吗？

步骤2：找出问题变数

现在我们已经确定在子问题之间存在一些递归结构。接下来，我们需要根据功能参数来表达问题，并查看其中哪些参数正在更改。

通常，在访谈中，您将拥有一个或两个变化的参数，但从技术上讲，它可以是任意数量。 one-changing-parameter问题的经典示例是“确定n-th斐波那契数”。 two-changing-parameters问题的此类示例是“计算字符串之间的编辑距离”。如果您不熟悉这些问题，请不必担心。

确定更改参数数量的一种方法是列出几个子问题的示例并比较参数。计算不断变化的参数数量对于确定我们必须解决的子问题数量很有价值。它本身也很重要，可以帮助我们加强对步骤1中的递归关系的理解。

在我们的示例中，每个子问题可能更改的两个参数是：

1. 阵列位置(P)
2. 速度(S)

可以说前面的跑道也在发生变化，但是考虑到整个不变的跑道和位置(P)已经携带了该信息，那将是多余的。

现在，有了这两个变化的参数和其他静态参数，我们对sub-problems有了完整的描述。

确定变化的参数并确定子问题的数量。

步骤3：清楚表达递归关系

这是许多人为了编码而急需完成的重要步骤。尽可能清晰地表达递归关系将增强您对问题的理解，并使其他所有事情都变得更加容易。

一旦确定了递归关系并根据参数指定了问题，这将是自然而然的步骤。问题如何相互联系？换句话说，假设您已经计算了子问题。您将如何计算主要问题？

这是我们在示例问题中的思考方式：

因为在跳到下一个位置之前您最多可以将速度调整为1，所以只有3种可能的速度，因此有3个点可以成为下一个位置。

更正式地说，如果我们的速度是S，即位置P，则可以从(S，P)转到：

1. (S，P + S); ＃如果我们不改变速度
2. (S_1，P + S_1); ＃如果我们将速度更改为-1
3. (S + 1，P + S + 1); ＃如果我们将速度更改+1

如果我们可以找到一种方法来停止上述任何子问题，那么我们也可以从(S，P)处停止。这是因为我们可以从(S，P)过渡到以上三个选项中的任何一个。

通常，这是对问题的很好理解(简单的英语解释)，但是有时您可能还希望用数学方式表达这种关系。让我们调用一个我们要计算canStop的函数。然后：

canStop(S，P)= canStop(S，P + S)|| canStop(S _1，P + S _1)|| canStop(S + 1，P + S + 1)

oo，看来我们有重复关系！

递归关系：假设您已经计算了子问题，那么您将如何计算主要问题？

步骤4：确定基本情况

基本案例是一个子问题，它不依赖于任何其他子问题。为了找到此类子问题，您通常需要尝试一些示例，看看您的问题如何简化为较小的子问题，并确定在什么时候无法进一步简化。

无法进一步简化问题的原因是，参数之一将变为在给定的情况下不可能的值约束问题。

在示例问题中，我们有两个变化的参数S和P。让我们考虑一下S和P的哪些可能的值不合法：

1. P应该在给定跑道的范围内
2. P不能表示跑道[P]为假，因为那将意味着我们正处于高峰
3. S不能为负，并且S == 0表示我们已经完成

有时，将我们对参数所做的断言转换为可编程基本情况可能会有些挑战。这是因为，如果要使代码看起来简洁而不检查不必要的条件，则除了列出断言之外，还需要考虑这些条件中的哪一个是可能的。

在我们的示例中：

1. P =跑道长度似乎是正确的事情。另一种选择是考虑P ==跑道尽头基本情况。但是，问题有可能分解成超出跑道末端的子问题，因此我们确实需要检查不平等性。
2. 这似乎很明显。我们可以简单地检查如果跑道[P]为假。
3. 与＃1类似，我们可以简单地检查SS == 0是S参数的足够基本情况。

第5步：确定您要迭代还是递归实现

到目前为止，我们谈论步骤的方式可能会让您认为我们应该递归地解决问题。但是，到目前为止，我们所讨论的一切都与您决定递归还是迭代实施该问题完全无关。在这两种方法中，您都必须确定递归关系和基本案例。

要决定是迭代还是递归，您需要仔细考虑一下trade-offs。

堆栈溢出问题通常是破坏交易的因素以及您不希望在(后端)生产系统中进行递归的原因。但是，出于访谈的目的，只要您提到trade-offs，通常都可以使用任何一种实现。您应该对两者都感到满意。

在我们的特定问题中，我实现了两个版本。这是为此的python代码：
递归解决方案：(可以找到原始代码段这里)

迭代解决方案：(可以找到原始代码段这里)

步骤6：添加备忘录

memory 化是与DP紧密相关的技术。它用于存储昂贵的函数调用的结果，并在再次出现相同的输入时返回缓存的结果。

我们为什么要在递归中添加备忘录？我们遇到相同的子问题，这些子问题在没有备忘的情况下被重复计算。这些重复经常导致指数时间复杂性。

在递归解决方案中，添加备忘录应该很简单。让我们看看为什么。请记住， memory 只是函数结果的缓存。有时您可能会偏离此定义以挤出一些次要的优化，但是将备忘录作为函数结果缓存是实现它的最直观的方法。

这意味着您应该：

1. 每次都将函数结果存储到内存中返回 声明
2. 在开始执行任何其他计算之前，先在内存中查找函数结果

这是上面添加了备注的代码(突出显示了几行)：(可以找到原始代码段这里)

为了说明 memory 和不同方法的有效性，让我们进行一些快速测试。我将对到目前为止已经看到的所有三种方法进行压力测试。设置如下：

1. 我创建了一个长度为1000的跑道，在随机位置出现尖峰(我选择在任何给定位置使尖峰的概率为20％)
2. initSpeed = 30
3. 我运行了所有功能10次，并测量了平均执行时间

结果如下(以秒为单位)：

您可以看到，纯递归方法所花的时间比迭代方法多500倍，比带 memory 的递归方法多1300倍。请注意，这种差异会随着跑道的长度而迅速增加。我鼓励您尝试自己运行它。

步骤7：确定时间复杂度

有一些简单的规则可以使动态编程问题的计算时间复杂度大大降低。您需要执行以下两个步骤：

1. 计算状态数-这取决于问题中更改参数的数量
2. 想想每个州完成的工作。换句话说，如果除一个状态外的所有其他内容都已计算，那么您需要做多少工作才能计算出最后一个状态？

在我们的示例问题中，状态数为| P | * | S |，哪里

• P是所有位置的集合(| P |表示P中的元素数)
• S是所有速度的集合

在此问题中，每个状态的工作量为O(1)，因为给定所有其他状态，我们只需查看3个子问题即可确定结果状态。

正如我们在前面的代码中指出的，| S |受跑道长度(| P |)的限制，因此我们可以说状态数为| P |²，并且由于每个状态所做的工作为O(1)，所以总时间复杂度为O(| P |²)。

但是，似乎| S |可以进一步限制，因为如果确实是| P |，很显然将无法停止，因为您必须在第一步中跳过整个跑道的长度。

因此，让我们看看如何对| S |进行更严格的限制。我们将最大速度称为S。假设我们从位置0开始。如果我们试图尽快停止并且忽略潜在的峰值，我们能停止多久？

在第一轮迭代中，我们必须至少将速度调整到零(S-1)，方法是将零速调整为-1。从那里我们至少要前进(S-2)步，依此类推。

对于跑道长度L，必须满足以下条件：

=> (S-1)+(S-2)+(S-3)+…。+ 1

=> S *(S-1)/2

=> S²— S — 2公升

如果找到上述函数的根，它们将是：

r1 = 1/2 + sqrt(1/4 + 2L)和r2 = 1/2-sqrt(1/4 + 2L)

我们可以将不等式写成：

(S — r1)*(S — r2)

考虑到S_r2>对于任何S> 0 0且L＞ 0，我们需要以下内容：

S — 1/2 —平方尺(1/4 + 2L)

=>小号

那是我们在长度为L的跑道上可能拥有的最大速度。如果速度高于该速度，则无论尖峰的位置如何，理论上我们都无法停止。

这意味着总时间复杂度仅取决于跑道L的长度，形式如下：

O(L * sqrt(L))比O(L²)好

O(L * sqrt(L))是时间复杂度的上限

太棒了，您成功了！