表格法

表格法

表格法是一种用于解决问题的方法。

表格法使用一个表格，其中首先存储最基本子问题的结果。然后，表格会不断填充更多的子问题结果，直到我们找到所求的完整问题的结果。

由于其先解决最基本子问题的方式，表格法被认为是以“自底向上”的方式解决问题的。

表格法是一种在 动态规划 中使用的技术，这意味着要使用表格法，我们必须解决的问题必须包含重叠的子问题。

使用表格法求 \(n\)th Fibonacci 数

Fibonacci 数 非常适合演示不同的编程技术，以及演示表格法的工作原理。

表格法使用一个表格，首先（自底向上）用最低的 Fibonacci 数 \(F(0)=0\) 和 \(F(1)=1\) 填充。下一个要存储在表格中的 Fibonacci 数是 \(F(2)=F(1)+F(0)\)。

下一个 Fibonacci 数始终是前面两个数字的和

\[ F(n)=F(n-1)+F(n-2) \]

通过这种方式，表格会不断用下一个 Fibonacci 数填充，直到我们找到所求的 \(n\)th Fibonacci 数。

def fibonacci_tabulation(n):
    if n == 0: return 0
    elif n == 1: return 1

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

    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]
    
    print(F)
    return F[n]
  
n = 10
result = fibonacci_tabulation(n)
print(f"\nThe {n}th Fibonacci number is {result}")

查找 \(n\)th Fibonacci 数的其他方法包括 递归，或者使用 记忆化 的改进版本。

表格法是一种自底向上方法

请参阅下面的图示，以更好地理解为什么表格法被称为“自底向上”方法。

作为比较，请参阅查找 \(n\)th Fibonacci 数的 “自顶向下”递归方法 的图示。

表格法从自底向上构建表格以查找第 10 个 Fibonacci 数，从 \(F(0)\) 和 \(F(1)\) 开始。

递归方法首先尝试查找 \(F(10)\)，但为了找到它，它必须调用 \(F(9)\) 和 \(F(8)\)，因此它一直向下直到 \(F(0)\) 和 \(F(1)\)，然后函数调用开始返回可以组合成最终答案的值。

其他用表格法解决的问题

就像查找 \(n\)th Fibonacci 数一样，表格法也可以用来解决其他问题

• 0/1 背包问题是关于拥有一组物品，我们可以将它们装入一个背包中，每个物品都有不同的价值。为了解决这个问题，我们需要找到能够最大化我们所装物品总价值的物品，但由于背包有重量限制，我们无法携带所有想要的物品。
• 最短路径问题可以使用 Bellman-Ford 算法 来解决，该算法也使用表格法来查找图中的最短路径。更具体地说，Bellman-Ford 算法的表格法体现在“距离”数组中的值如何被更新。
• 旅行商问题可以使用 Held-Karp 算法精确解决，该算法也使用表格法。该算法未在此教程中进行描述，因为它虽然优于穷举法 \(O(n!)\)，但仍然效率不高 \(O(2^n n^2)\)，并且相当复杂。

动态规划中的表格法

如开头所述，表格法（就像记忆化一样）是用于 动态规划 的技术。

动态规划是一种设计算法来解决问题的方法。

为了使动态规划起作用，我们要解决的问题必须具备以下两个特性

• 问题必须由较小的、重叠的子问题构成。例如，Fibonacci 数 \(F(3)\) 的解与 Fibonacci 数 \(F(2)\) 和 \(F(1)\) 的解重叠，因为我们通过组合 \(F(2)\) 和 \(F(1)\) 来得到 \(F(3)\)。
• 问题还必须具有最优子结构，这意味着问题的解可以从其子问题的解中构建出来。在查找 \(n\)th Fibonacci 数时，可以通过将 \(F(n-1)\) 和 \(F(n-2)\) 相加来得到 \(F(n)\)。因此，仅知道前两个数字不足以找到 \(F(n)\)，我们还必须知道结构，以便知道如何将它们组合起来。

在 下一页 上阅读更多关于动态规划的内容。