动态规划

动态规划

动态规划（Dynamic Programming）是一种设计算法的方法。

使用动态规划设计的算法将问题分解为子问题，找到子问题的解，并将它们组合起来形成我们想解决的完整问题的解决方案。

我们在此教程中已经见过动态规划，在 记忆化（memoization） 和 制表（tabulation） 技术中，以及用于解决 0/1 背包问题 或使用 Bellman-Ford 算法 找到 最短路径 等问题。

使用动态规划找到第 \(n\) 个斐波那契数

假设我们想要一个查找第 \(n\) 个斐波那契数的算法。我们还不知道如何找到第 \(n\) 个斐波那契数，除了我们想使用动态规划来设计算法。

那么，我们如何使用动态规划来设计一个查找第 \(n\) 个斐波那契数的算法呢？

没有严格的规则说明如何使用动态规划来设计算法，但以下建议在大多数情况下都适用：

1. 检查问题是否具有“重叠子问题”和“最优子结构”。
2. 解决最基本的子问题。
3. 找到一种将子问题的解组合起来形成新子问题解的方法。
4. 编写算法（逐步过程）。
5. 实现算法（测试其是否有效）。

我们来动手做吧。

步骤 1：检查问题是否具有“重叠子问题”和“最优子结构”。

在尝试使用动态规划查找算法之前，我们必须首先检查问题是否具有“重叠子问题”和“最优子结构”这两个特性。

重叠子问题？

是的。第 6 个斐波那契数是第 5 个和第 4 个斐波那契数的组合：\(8=5+3\)。并且这个规则适用于所有其他斐波那契数。这表明查找第 \(n\) 个斐波那契数的问题可以分解为子问题。

此外，子问题是重叠的，因为 \(F(5)\) 基于 \(F(4)\) 和 \(F(3)\)，而 \(F(6)\) 基于 \(F(5)\) 和 \(F(4)\)。

\[ \begin{equation} \begin{aligned} F(5) {} & =\underline{F(4)}+F(3) \\ 5 & =\underline{3}+2 \\\\ & 并且 \\\\ & \\\\ F(6) & =F(5)+\underline{F(4)} \\ 8 & =5+\underline{3} \end{aligned} \end{equation} \]

您看？子问题 \(F(5)\) 和 \(F(6)\) 的解都是使用 \(F(4)\) 的解创建的，而且这种情况有很多，因此子问题也重叠。

最优子结构？

是的，斐波那契数列具有非常清晰的结构，因为前两个数字相加会产生下一个斐波那契数，并且除了前两个数之外，这适用于所有斐波那契数。这意味着我们知道如何通过组合子问题的解来构建解决方案。

我们可以得出结论，查找第 \(n\) 个斐波那契数的问题满足这两个要求，这意味着我们可以使用动态规划来查找解决该问题的算法。

步骤 2：解决最基本的子问题。

现在我们可以开始尝试使用动态规划查找算法了。

先解决最基本的子问题是一个好主意，可以帮助我们了解算法应该如何运行。

在查找第 \(n\) 个斐波那契数的问题中，找到最基本的子问题并不难，因为我们已经知道：

\[ F(0)=0 \\ F(1)=1 \\ F(2)=1 \\ F(3)=2 \\ F(4)=3 \\ F(5)=5 \\ F(6)=8 \\ ... \]

步骤 3：找到一种将子问题的解组合起来形成新子问题解的方法。

在这一步，对于我们的问题，如何组合子问题非常简单，我们只需要将前两个斐波那契数相加即可得到下一个。

例如，第二个斐波那契数是通过将前两个数字相加得到的 \(F(2)=F(1)+F(0)\)，并且这通常也是通用规则，如前所述：\(F(n)=F(n-1)+F(n-2)\)。

步骤 4：编写算法（逐步过程）。

与其直接写出算法的文本，不如先尝试编写一个解决特定问题的过程，例如查找第 6 个斐波那契数。

作为参考，前 8 个斐波那契数是：\(0,\; 1,\; 1,\; 2,\; 3,\; 5,\; \underline{8},\; 13\)。

查找第 6 个斐波那契数，我们可以从前两个数字 0 和 1 开始，它们出现在数列的第 0 位和第 1 位，并将它们放入一个数组，分别在索引 0 和 1。然后，我们可以将数组中的前两个数字相加来生成下一个数字，并将新生成的数字作为一个新元素推入数组。如果我们一直这样做，直到数组包含 7 个元素，我们就停止并返回 F[6]。这样可行，对吧？

在解决了上面的特定问题之后，现在更容易编写实际的算法了。

以动态规划为设计方法，查找第 \(n\) 个斐波那契数的算法可以描述如下：

步骤 5：实现算法（测试其是否有效）。

为了实现上述算法，我们假设函数的参数 n 是一个正数（第 \(n\) 个斐波那契数）。我们使用一个 for 循环来创建新的斐波那契数，并且如果函数以 0 或 1 作为参数调用，我们会立即返回基本情况 F[0] 和 F[1]。

实现算法也意味着我们可以检查它是否有效。

def nth_fibo(n):
    if n==0: return 0
    if n==1: return 1

    F = [None] * (n + 1)
    F[0] = 0
    F[1] = 1

    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]

    return F[n]

n = 6
result = nth_fibo(n)
print(f"The {n}th Fibonacci number is {result}")

看！

我们已将动态规划用作设计方法，创建了一个查找第 \(n\) 个斐波那契数的算法。

我们还实现了该算法以证明其有效性，在此过程中，我们无意中使用了动态规划中一种成熟的技术，称为 制表（tabulation），其中通过自下而上地解决子问题来找到解决方案，使用某种表格。

此外，我们避免了多次计算相同的重叠子问题，例如 F[3]，这如果我们采用 蛮力递归方法 等，则可能会发生。

动态规划中使用的另一种技术称为 记忆化（memoization）。在这种情况下，使用记忆化实际上是用蛮力递归地解决问题，但它会在算法运行时存储子问题的解，以避免重复执行相同的计算。

动态规划中使用的技术

使用动态规划设计算法可能很困难，但动态规划的概念实际上并不难：解决问题，但由于子问题是重叠的，所以要以一种聪明的方式来解决，确保特定的子问题只被求解一次。

为了能够在动态规划中使用先前已解决子问题的解决方案，必须以某种方式存储先前找到的解决方案，这可以通过 记忆化（memoization） 或 制表（tabulation） 来实现。

记忆化（Memoization）是动态规划中使用的技术，其中解决方案是递归找到的。当算法运行时，会存储子问题的解，在尝试计算子问题的解之前，它会首先检查该解是否已计算过，以避免重复计算。

记忆化技术被称为“自顶向下”（top-down），因为初始函数调用是针对主问题的，它会导致调用更小、更小的子问题。

制表（Tabulation）是动态规划中使用的技术，其中将重叠子问题的解存储在一个表格（数组）中，从最基本的子问题开始。

制表技术不是递归的，它被称为“自底向上”（bottom-up），因为它构建最终解决方案的方式是从解决最基本的子问题开始。由于最基本的子问题解首先存储在表格中，当稍后解决依赖于先前子问题的子问题时，算法可以从表格中直接拾取这些解，无需再次计算。

为了更好地理解记忆化是如何工作的（被认为是“自顶向下”），以及制表是如何工作的（被认为是“自底向上”），请看下面的两张图。

如上图所示，制表方法从底部开始，先求解 F(0)，而记忆化方法从顶部开始，求解 F(10)，然后将其分解为越来越小的子问题。