动态规划面试题

1) 什么是动态规划？

动态规划的思路是，当我们用给定的输入解决了一个问题，然后保存结果供以后参考，以避免重复解决同一个问题。动态规划是由Richard Bellman开发的。

在动态规划的世界里，动态规划是一种强大的技术，它允许我们在多项式时间内解决各种各样的问题，而朴素的方法可能需要指数时间。

例如，如果我们以斐波那契数列为例，其中每个数字是前两个数字之和。斐波那契数列是0, 1, 1, 2, 3, 5, 8，依此类推。如果我们被要求计算第 n 个斐波那契数。我们可以使用以下递推公式来计算它：

Fib(n) = n, 如果 n<2

fib(n-1) + fib(n-2), 否则

在朴素方法的情况下，斐波那契函数的实现的时间复杂度是 O(2^n)，而动态规划方法的解决方案仅需 O(n) 时间即可实现相同的功能。

2) 动态规划的特点是什么？

动态规划的特点如下：

• 最优子结构： 如果整体的最优解可以从所有子问题的最优解中得到，那么这个问题就具有最优子结构性质。
• 重叠子问题： 当一个大问题被分解成小问题时，这些小问题就称为子问题。让我们以计算 Fib(4) 为例。 Fib(4) 是通过将 Fib(3) 和 Fib(2) 的值相加得到的，Fib(3) 是通过将 Fib(2) 和 Fib(1) 相加得到的，Fib(2) 是通过将

3) 有哪些动态规划方法？

我们可以使用以下两种方法来优化问题：

• 自顶向下方法
• 自底向上方法

自顶向下方法

• 自顶向下方法是通过递归地找到小问题的解决方案来解决大问题的技术。
• 当找到子问题的解决方案后，问题的结果就会被存储或缓存，这样我们就不需要多次计算结果。与其计算结果，我们只需要返回缓存的结果。
• 这种存储已解决子问题结果的方法称为记忆化。

让我们通过有记忆化和无记忆化的例子来理解这种方法。

无记忆化

在上面的代码中，我们使用了递归方法来找出斐波那契数列。当 'n' 的值增加时，函数调用也会增加，计算量也会增加。在这种情况下，时间复杂度呈指数增长，达到 2^n。

有记忆化

在上面的代码中，我们声明了一个名为 'memo' 的数组。我们声明这个数组是为了存储子问题的结果。这解决了计算已计算子问题解的问题。

4) 动态规划的应用有哪些？

以下是动态规划的应用列表：

• 谷歌地图： 假设我们每天都要从家去办公室。第一天，我们会考虑所有可能的路线来计算最短路径。每天重新计算最短路径是不可能的，所以我们会记住最短路径。谷歌地图使用动态规划方法来确定源和目的地之间的最短路径。
• 最长公共子序列： 在这里，最长意味着它应该是所有子序列中最大的。公共意味着会给定两个字符串，我们需要找到两个子序列之间的公共部分。子序列是字符串中的字符序列，并且这个字符序列应该相对于它们的位置是递增的。
  如何创建子序列？
  请看以下示例
  W = a b c d
  = ab, bd, ac, ad, bd, acd, bcd, abcd
  以上是由字符串“a b c d”可以构成的子序列。子序列 ca, db 是错误的，因为子序列应该是按照它们位置递增的顺序构成的。例如，字符 'c' 在字符串中出现在 'a' 之后，所以 'ca' 子序列是不可能的。字符 'd' 在字符串中出现在 'b' 之后，所以 'db' 子序列也是不可能的。从字符串中可能产生的子序列总数为 2^n
  其中 'n' 是字符串中的字符数。
• 最长递增子序列问题： 最长递增子序列问题是用于从给定序列中找到最长子序列的问题，其中子序列中的所有元素都按递增顺序排序。
• 背包问题： 在分治策略中，问题被分解成子问题，这些子问题进一步被分解成子问题。这个分解过程将继续进行，直到我们达到可以轻松解决的子问题。在这个过程中，我们可能会多次遇到相同的子问题。
  上述问题的解决方案是使用背包动态规划技术。使用背包问题的想法是将解决方案存储在已解决子问题的表中。如果我们再次遇到相同的子问题，我们只需从表中获取子问题的解决方案，而无需再次解决它。因此，我们可以说动态规划算法非常有效。
  以下是解决问题需要执行的任务：
• 首先，我们将找到子问题的解决方案。
• 然后，我们将找到构建子问题解决方案的公式。
• 在此步骤中，我们将创建一个表来存储子问题的解决方案。计算子问题的解决方案并将解决方案存储在表中。
• 一旦所有子问题都得到解决，我们将找到原始问题的解决方案。

5) 自顶向下方法和自底向上方法有什么区别？

以下是自顶向下方法和自底向上方法之间的区别列表：

6) 动态规划和贪婪方法有什么区别？

以下是动态规划和贪婪方法之间的区别列表：

7) 动态规划和分治法有什么区别？

以下是动态规划和分治法之间的区别列表：

8) 动态规划与记忆化和递归有什么区别？

递归是反复调用函数的过程。记忆化是存储已解决子问题解决方案的技术。动态规划是通过存储已解决子问题的解决方案来解决递归的技术。

9) 什么是回文最长子序列？

回文最长子序列问题是给定一个序列，我们需要找到回文最长子序列的长度。子序列是从主序列中选取一些或所有元素而不改变元素顺序而形成的序列。这里的回文子序列意味着元素从两个方向（即向前和向后）看起来相同。

让我们通过一个例子来理解这个问题。

假设我们有一个输入“bbbab”。

以下是可以从上述序列中构成的回文子序列：

bbbb

bbb

bab

由于子序列“bbbb”包含的字符数最多，即 4 个；因此，回文最长子序列是“bbbb”。

10) 问题陈述

给定两个字符串 s1 和 s2。我们需要找到字符串 s1 和 s2 之间的最长公共子序列。

例如

S1：“ACBEA”

S2：“ADCA”

要开始解决这个问题，让我们从字符串的末尾逐个字符匹配。

LCS("ACBEA", "ADCA") = 1 + LCS("ACBE", "ADC")

由于字符 'A' 在两个字符串中都存在，所以我们从两个字符串中都删除字符 'A'。我们将 1 加上 "ACBE" 和 "ADC" 的 LCS。因此，当字符匹配时，我们删除匹配的字符并找出剩余字符串的 LCS。我们加上 1，因为两个字符都匹配。

LCS("ACBE", "ADC") = max(LCS(ACB, ADC), LCS(ACBE, AD))

在上面的例子中，字符 'E' 和 'C' 都是不同的。所以，我们首先从字符串 ACBE 中删除字符，然后计算 LCS。然后，我们从字符串 ADC 中删除字符。最后，我们考虑上述两个 LCS 的最大值。

这里我们遵循了以下两个规则：

• 如果字符匹配，我们加上 1 并删除匹配的字符。
• 如果字符不匹配，我们丢弃字符并计算 LCS 的最大值。

上述方法可以通过递归或使用动态规划方法来实现。由于递归方法包含大量的比较，导致指数复杂度，因此最好使用动态规划方法。

我们考虑以下表格：

指针表

上面是一个指针表，我们在这里记录匹配表的移动。我们将使用这个指针表来生成字符串的 LCS。

以下是我们在此处使用的规则：

• 最后一个字符匹配： 我们将从两个字符串中删除匹配的字符，然后将 1 加到修剪后的字符串的 LCS 上。
• 最后一个字符不匹配： 我们一次删除一个字符，然后取两种组合的 LCS 的最大值。

让我们通过初始化开始处理这些矩阵。

首先，我们将两个矩阵都初始化为零。

现在我们从第一行开始。由于两个字符串的 'A' 都匹配，所以在第一个表中加 1。我们正在从两个字符串中删除字符，所以我们可以选择其中任何一个字符串，s1 或 s2。

删除 'D' 字符

在上面的例子中，我们增加计数并继续前进。现在我们考虑的字符串是 A 和 AD。由于两个字符串中的字符 A 和 D 都不匹配，所以我们只能删除其中一个字符串。如果我们从字符串 s1 中删除 A，我们就得到一个空字符串，然后我们比较 s2 中的 A 和 D；空字符串和 AD 的 LCS 为零。如果我们从字符串 s2 中删除 D，则 A 和 AD 的 LCS 为 1，即 A 和 A 的 LCS。

由于我们正在从字符串 s2 中删除字符 'D'，所以在指针表的 D 列中添加字符串 s1。这里我们应用了一个规则，即如果我们一次只删除一个字符，那么如果我们删除 s1，我们就放入 s2，如果我们删除 s2，我们就放入 s1。如果我们删除两个字符，我们可以删除 s1 或 s2。

删除 'C' 字符

现在，A 和 C 不匹配，所以我们增加一个计数器，如下所示。由于我们正在从字符串 s2 中删除字符 C，所以我们在 C 列下的指针表中添加 s2。我们移到 A 列。

删除 'A' 字符

在这种情况下，两个字符串的 A 字符匹配，所以我们增加计数器，如下所示。这里我们正在从两个字符串中删除字符，所以我们可以添加 s1 或 s2。计数器增加后，我们向下移动。

现在我们考虑的字符串是 **AC** 和 **A**。如果我们从字符串 s2 中删除 A，我们就得到一个空字符串；空字符串和 AC 的 LCS 为零。如果我们从字符串 s1 中删除 C，则 A 和 AC 的 LCS 等于 1，如下所示。计数器增加后，我们继续前进。

现在我们考虑的字符串是 AC 和 AD。在这种情况下，我们可以删除 C 或 D。如果我们删除 C，则 A 和 AD 的 LCS 为 1；如果我们删除 D，则 AC 和 A 的 LCS 为 1。在两种情况下，LCS 的值都为 1。因此，我们可以删除其中任何一个字符串，即 C 和 D。假设我们删除字符串 C，则 A 和 AD 的 LCS 为 1，所以在指针表中显示 1 和 s2，如下所示。

现在我们考虑的字符串是 AC 和 ADC。由于两个字符串的 C 字符都匹配，所以我们必须删除这两个字符串。AC 和 ADC 的 LCS 现在等于 1 加上 A 和 AD 的 LCS。由于 A 和 AD 的 LCS 为 1，所以 AC 和 ADC 的 LCS 等于 2。由于我们正在删除两个字符串，所以我们可以将任何一个字符串添加到指针表中，如下所示。

现在我们考虑的字符串是 AC 和 ADCA。由于两个字符串的 C 和 A 字符都不同，所以我们可以删除 C 或 A。如果我们删除 A，则 AC 和 ADC 的 LCS 为 2；如果我们删除 C，则 A 和 ADCA 的 LCS 为 1。我们必须考虑最大 LCS。这里，最大 LCS 是 2；因此，AC 和 ADCA 的 LCS 等于 2。这里，我们正在删除字符串 s2，所以我们需要在指针表中添加 s1，如下所示。

指针向下移动。现在我们考虑的字符串是 ACB 和 A。由于两个字符 B 和 A 都不匹配，所以我们可以删除 B 和 A。如果我们删除 A，它将导致一个空字符串。如果我们删除 B，则 ACB 和 A 的 LCS 等于 AC 和 A 的 LCS，即 1，如下所示。在这种情况下，我们正在删除 s1 字符串，所以我们必须在指针表中添加 s2。指针向前移动。

现在我们考虑的字符串是 ACB 和 AD。由于两个字符 B 和 D 都不匹配，所以我们可以删除 B 或 D。如果我们删除 B，则 AC 和 AD 的 LCS 为 1；如果我们删除 D，则 ACB 和 A 的 LCS 为 1。在两种情况下，LCS 的值都为 1，所以我们可以删除其中任何一个字符串。ACB 和 AD 的 LCS 等于 1，如下所示。

现在我们考虑的字符串是 ACB 和 ADC。由于两个字符 B 和 C 都不匹配，所以我们可以删除 B 和 C。如果我们删除 B，则 AC 和 ADC 的 LCS 为 2；如果我们删除 C，则 ACB 和 AD 的 LCS 为 1。由于 2>1；因此，ACB 和 ADC 的 LCS 等于 2。

现在我们考虑的字符串是 ACB 和 ADCA。由于两个字符 B 和 A 都不匹配，所以我们可以删除 B 和 A。如果我们删除 B，则 AC 和 ADCA 的 LCS 为 2；如果我们删除 A，则 ACB 和 ADC 的 LCS 为 2。由于两个 LCS 都相同，所以我们可以删除其中任何一个字符串。ACB 和 ADCA 的 LCS 为 2。

ACB 和 ADC 的 LCS 等于 2。

现在我们考虑的字符串是 ACBE 和 A。由于两个字符 E 和 A 都不同，所以我们可以删除 E 或 A。如果我们删除 E，则 ACB 和 A 的 LCS 为 1。如果我们删除 A，我们将得到一个空字符串，LCS 将变为 0。由于 1>0；因此，ACBE 和 A 的 LCS 等于 ACB 和 A 的 LCS，即 1。

现在我们考虑的字符串是 ACBE 和 AD。由于两个字符 E 和 D 都不匹配，所以我们可以删除 E 和 D。如果我们删除 E，则 ACB 和 AD 的 LCS 为 1。如果我们删除 D，则 ACBE 和 A 的 LCS 为 1。由于两种情况下的 LCS 都相同，所以我们可以删除其中任何一个字符串。因此，ACBE 和 AD 的 LCS 值均为 1，并且在指针表中可以添加任何一个字符串 s1 或 s2，如下所示。

现在我们考虑的字符串是 ACBE 和 ADC。由于两个字符 E 和 C 都不匹配，所以我们可以删除 E 或 C。如果我们删除 E，则 ACB 和 ADC 的 LCS 为 2。如果我们删除 C，则 ACBE 和 AD 的 LCS 为 1。由于 2>1；因此，ACBE 和 AD 的 LCS 等于 ACB 和 ADC 的 LCS，即 2。

现在我们考虑的字符串是 ACBE 和 ADCA。由于两个字符 E 和 A 都不匹配，所以我们可以删除 E 或 A。如果我们删除 E，则 ACB 和 ADCA 的 LCS 为 2。如果我们删除 A，则 ACBE 和 ADC 的 LCS 为 1。由于 2>1；因此，ACBE 和 ADCA 的 LCS 等于 ACB 和 ADCA 的 LCS，即 2。

现在我们考虑的字符串是 ACBEA 和 A。由于两个字符都匹配，即 A，所以我们需要删除这两个字符串。ACBEA 和 A 的 LCS 值将更新为 1，并且可以在指针表中添加任何一个字符串，即 s1 或 s2，如下所示。

现在我们考虑的字符串是 ACBEA 和 AD。由于两个字符 A 和 D 都不匹配，所以我们可以删除其中任何一个字符串。如果我们删除 D，则 ACBEA 和 A 的 LCS 值为 1。如果我们删除 A，则 ACBE 和 AD 的 LCS 值为 1。由于两种情况下的 LCS 值都相同，即 1；因此，ACBEA 和 AD 的 LCS 值等于 1。我们可以在指针表中添加任何一个字符串，如下所示。

现在我们考虑的字符串是 ACBEA 和 ADC。由于两个字符 A 和 C 都不同，所以我们可以删除其中任何一个字符串。如果我们删除 A，则 ACBE 和 ADC 的 LCS 值为 2。如果我们删除 C，则 ACBEA 和 AD 的 LCS 值为 1。由于 2>1；因此，ACBEA 和 ADC 的 LCS 值等于 ACBE 和 ADC 的 LCS 值，即 2。在这种情况下，我们正在删除 s1，所以我们将 s2 添加到指针表中，如下所示。

现在我们考虑的字符串是 ACBEA 和 ADCA。由于两个字符串的最后一个字符 A 都匹配，所以我们必须删除这两个字符串。因此，ACBEA 和 ADCA 的 LCS 等于 (1 + ACBE 和 ADC 的 LCS，即 2) 3。

我们得出结论，最长公共子序列的长度是 3。现在我们需要确定子序列。以下是用于确定子序列的规则：

• 如果指针表包含 s1/s2 字符串，那么我们必须向上对角线移动。
• 如果指针表包含字符串 s1，那么我们必须向左移动。
• 如果指针表包含字符串 s2，那么我们必须向上移动。

由于指针指向最后一行和最后一列，并且值为 s1/s2。所以，指针将沿对角线移动，指向字符串 s2，如下所示。

现在指针指向字符串 s2，所以指针将向上移动，指向字符串 s2，如下所示。

由于指针指向字符串 s2，所以指针将向上移动，指向字符串 s1/s2，如下所示。

由于指针指向字符串 s1/s2，所以指针将沿对角线向上移动，指向字符串 s1，如下所示。

由于指针指向字符串 s1，将向左移动，指向字符串 s1/s2，如下所示。

从上表我们可以看出，最长公共子序列是 ACA。

11) 记忆化或自顶向下方法的优缺点是什么？

优点

• 它非常容易理解和实现。
• 它只在需要时才解决子问题。
• 它易于调试。

缺点

它使用递归技术，在调用堆栈中占用更多内存。有时当递归太深时，会发生堆栈溢出条件。

它占用更多内存，从而降低了整体性能。

12. 在为同一个问题选择自顶向下方法和自底向上方法的解决方案时，我们应该考虑哪种方法？

以下是我们在决定算法时考虑的两个因素：

• 时间复杂度： 由于两种方法的时间复杂度相似，但 for 循环比递归函数调用更便宜。因此，我们可以说自底向上方法在机器时间方面比自顶向下方法更快。
• 空间复杂度： 当我们不考虑自顶向下方法中的额外调用堆栈分配时。主要是这两种方法都用于为所有子解决方案构建一个表，但自底向上方法遵循拓扑顺序，其中辅助空间的成本可以减小到问题直接依赖项的大小。例如，fibonacci(n)= fibonacci(n-1) + fibonacci(n-2)，这里我们只存储了两次之前的计算。