表格化

表格化

表格化是一种用于解决问题的技术。

表格化使用一个表格，其中首先存储了最基本子问题的结果。然后，表格会逐渐填充更多子问题的结果，直到我们找到我们要查找的完整问题的结果。

表格化技术被称为“自底向上”解决问题，因为它首先解决最基本子问题。

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

使用表格化查找第\(n\)个斐波那契数

斐波那契数列非常适合演示不同的编程技术，也适合演示表格化的工作原理。

表格化使用一个表格，该表格首先填充最低的斐波那契数\(F(0)=0\)和\(F(1)=1\)(自底向上)。下一个要存储在表格中的斐波那契数是\(F(2)=F(1)+F(0)\)。

下一个斐波那契数始终是前两个数的总和

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

以此类推，表格会继续填充下一个斐波那契数，直到我们找到我们要查找的第\(n\)个斐波那契数。

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\)个斐波那契数的其他方法包括递归，或使用记忆化的改进版本。

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

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

作为参考，请参阅“自顶向下”递归方法的绘图，用于查找第\(n\)个斐波那契数。

表格化方法从自底向上构建表格，以找到第 10 个斐波那契数，从\(F(0)\)和\(F(1)\)开始。

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

使用表格化解决的其他问题

就像查找第\(n\)个斐波那契数一样，表格化也可以用来找到其他问题的解决方案

• 0/1 背包问题是指我们有一组可以装进背包（一个简单的背包）的物品，每个物品都有不同的价值。为了解决这个问题，我们需要找到将我们装入的物品的总价值最大化的物品，但我们不能带走所有我们想要的物品，因为背包有重量限制。
• 最短路径问题可以使用贝尔曼-福特算法解决，该算法也使用表格化来查找图中的最短路径。更具体地说，贝尔曼-福特算法的表格化方法在于如何更新“距离”数组中的值。
• 旅行推销员问题可以使用赫尔德-卡普算法精确解决，该算法也使用表格化。本教程中没有介绍此算法，因为它虽然比暴力法\(O(n!)\)更好，但仍然不太有效\(O(2^n n^2)\)，而且相当高级。

动态规划中的表格化

如顶部所述，表格化（就像记忆化一样）是一种在称为动态规划的方法中使用的技术。

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

为了使动态规划有效，我们要解决的问题必须具备以下两个属性

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

阅读下一頁的动态规划 了解更多信息。