hello-algo/zh-hant/docs/chapter_dynamic_programming/intro_to_dynamic_programming.md

初探動態規劃

動態規劃（dynamic programming）是一個重要的演算法範式，它將一個問題分解為一系列更小的子問題，並透過儲存子問題的解來避免重複計算，從而大幅提升時間效率。

在本節中，我們從一個經典例題入手，先給出它的暴力回溯解法，觀察其中包含的重疊子問題，再逐步導出更高效的動態規劃解法。

!!! question "爬樓梯"

給定一個共有 $n$ 階的樓梯，你每步可以上 $1$ 階或者 $2$ 階，請問有多少種方案可以爬到樓頂？

如下圖所示，對於一個 3 階樓梯，共有 3 種方案可以爬到樓頂。

本題的目標是求解方案數量，我們可以考慮透過回溯來窮舉所有可能性。具體來說，將爬樓梯想象為一個多輪選擇的過程：從地面出發，每輪選擇上 1 階或 2 階，每當到達樓梯頂部時就將方案數量加 1 ，當越過樓梯頂部時就將其剪枝。程式碼如下所示：

[file]{climbing_stairs_backtrack}-[class]{}-[func]{climbing_stairs_backtrack}

方法一：暴力搜尋

回溯演算法通常並不顯式地對問題進行拆解，而是將求解問題看作一系列決策步驟，透過試探和剪枝，搜尋所有可能的解。

我們可以嘗試從問題分解的角度分析這道題。設爬到第 i 階共有 dp[i] 種方案，那麼 dp[i] 就是原問題，其子問題包括：

$$ dp[i-1], dp[i-2], \dots, dp[2], dp[1]

由於每輪只能上 1 階或 2 階，因此當我們站在第 i 階樓梯上時，上一輪只可能站在第 i - 1 階或第 i - 2 階上。換句話說，我們只能從第 i -1 階或第 i - 2 階邁向第 i 階。

由此便可得出一個重要推論：爬到第 i - 1 階的方案數加上爬到第 i - 2 階的方案數就等於爬到第 i 階的方案數。公式如下：

$$ dp[i] = dp[i-1] + dp[i-2]

這意味著在爬樓梯問題中，各個子問題之間存在遞推關係，原問題的解可以由子問題的解構建得來。下圖展示了該遞推關係。

我們可以根據遞推公式得到暴力搜尋解法。以 dp[n] 為起始點，遞迴地將一個較大問題拆解為兩個較小問題的和，直至到達最小子問題 dp[1] 和 dp[2] 時返回。其中，最小子問題的解是已知的，即 $dp[1] = 1$、dp[2] = 2 ，表示爬到第 $1$、2 階分別有 $1$、2 種方案。

觀察以下程式碼，它和標準回溯程式碼都屬於深度優先搜尋，但更加簡潔：

[file]{climbing_stairs_dfs}-[class]{}-[func]{climbing_stairs_dfs}

下圖展示了暴力搜尋形成的遞迴樹。對於問題 dp[n] ，其遞迴樹的深度為 n ，時間複雜度為 O(2^n) 。指數階屬於爆炸式增長，如果我們輸入一個比較大的 n ，則會陷入漫長的等待之中。

觀察上圖，指數階的時間複雜度是“重疊子問題”導致的。例如 dp[9] 被分解為 dp[8] 和 dp[7] ，dp[8] 被分解為 dp[7] 和 dp[6] ，兩者都包含子問題 dp[7] 。

以此類推，子問題中包含更小的重疊子問題，子子孫孫無窮盡也。絕大部分計算資源都浪費在這些重疊的子問題上。

方法二：記憶化搜尋

為了提升演算法效率，我們希望所有的重疊子問題都只被計算一次。為此，我們宣告一個陣列 mem 來記錄每個子問題的解，並在搜尋過程中將重疊子問題剪枝。

1. 當首次計算 dp[i] 時，我們將其記錄至 mem[i] ，以便之後使用。
2. 當再次需要計算 dp[i] 時，我們便可直接從 mem[i] 中獲取結果，從而避免重複計算該子問題。

程式碼如下所示：

[file]{climbing_stairs_dfs_mem}-[class]{}-[func]{climbing_stairs_dfs_mem}

觀察下圖，經過記憶化處理後，所有重疊子問題都只需計算一次，時間複雜度最佳化至 $O(n)$ ，這是一個巨大的飛躍。

方法三：動態規劃

記憶化搜尋是一種“從頂至底”的方法：我們從原問題（根節點）開始，遞迴地將較大子問題分解為較小子問題，直至解已知的最小子問題（葉節點）。之後，透過回溯逐層收集子問題的解，構建出原問題的解。

與之相反，動態規劃是一種“從底至頂”的方法：從最小子問題的解開始，迭代地構建更大子問題的解，直至得到原問題的解。

由於動態規劃不包含回溯過程，因此只需使用迴圈迭代實現，無須使用遞迴。在以下程式碼中，我們初始化一個陣列 dp 來儲存子問題的解，它起到了與記憶化搜尋中陣列 mem 相同的記錄作用：

[file]{climbing_stairs_dp}-[class]{}-[func]{climbing_stairs_dp}

下圖模擬了以上程式碼的執行過程。

與回溯演算法一樣，動態規劃也使用“狀態”概念來表示問題求解的特定階段，每個狀態都對應一個子問題以及相應的區域性最優解。例如，爬樓梯問題的狀態定義為當前所在樓梯階數 i 。

根據以上內容，我們可以總結出動態規劃的常用術語。

• 將陣列 dp 稱為 dp 表，dp[i] 表示狀態 i 對應子問題的解。
• 將最小子問題對應的狀態（第 1 階和第 2 階樓梯）稱為初始狀態。
• 將遞推公式 dp[i] = dp[i-1] + dp[i-2] 稱為狀態轉移方程。

空間最佳化

細心的讀者可能發現了，由於 dp[i] 只與 dp[i-1] 和 dp[i-2] 有關，因此我們無須使用一個陣列 dp 來儲存所有子問題的解，而只需兩個變數滾動前進即可。程式碼如下所示：

[file]{climbing_stairs_dp}-[class]{}-[func]{climbing_stairs_dp_comp}

觀察以上程式碼，由於省去了陣列 dp 佔用的空間，因此空間複雜度從 O(n) 降至 O(1) 。

在動態規劃問題中，當前狀態往往僅與前面有限個狀態有關，這時我們可以只保留必要的狀態，透過“降維”來節省記憶體空間。這種空間最佳化技巧被稱為“滾動變數”或“滾動陣列”。