動態規劃

動態規劃

動態規劃（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)，然後將其分解為越來越小的子問題。