表格法

表格法

表格法是一種用於解決問題的方法。

表格法使用一個表格，其中首先儲存最基本子問題的結果。然後，表格會不斷填充更多的子問題結果，直到我們找到所求的完整問題的結果。

由於其先解決最基本子問題的方式，表格法被認為是以“自底向上”的方式解決問題的。

表格法是一種在 動態規劃 中使用的技術，這意味著要使用表格法，我們必須解決的問題必須包含重疊的子問題。

使用表格法求 \(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)\)，我們還必須知道結構，以便知道如何將它們組合起來。

在 下一頁 上閱讀更多關於動態規劃的內容。