Learning Objectives
- 從費氏數列的遞迴樹看出重疊子問題，說明直接遞迴為什麼很慢
- 用記憶化（由上而下）和表格法（由下而上）把費氏數列改成 O(n)
- 說明動態規劃適用的兩個條件：重疊子問題與最佳子結構
- 依「定義狀態、寫出轉移式、設定初始值、決定計算順序」四個步驟，解爬樓梯、方格路徑與找零問題
- 用額外記錄的陣列，還原最佳解實際的做法
同一個問題算了好多遍
費氏數列（Fibonacci）的定義是：fib(0) = 0、fib(1) = 1，之後每一項是前兩項的和：0, 1, 1, 2, 3, 5, 8, 13, … 照定義直接寫成遞迴（第 05 課）只要三行：
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
程式正確，但非常慢：fib(40) 要呼叫自己超過 3 億次。原因在遞迴樹裡：算 fib(6) 要算 fib(5) 和 fib(4)， 而 fib(5) 自己又要再算一次 fib(4)。同一個子問題被算了一遍又一遍，呼叫次數大約隨 n 以指數成長。
這一課的主角動態規劃（dynamic programming，DP）就是解決這件事的方法：每個子問題只算一次，把答案記下來，之後直接查。
直接遞迴：fib(6) 呼叫了幾次
看遞迴樹長出來的過程。fib(4) 出現 2 次、fib(3) 出現 3 次、fib(2) 出現 5 次，每一次都從頭重算。算 fib(6) 總共呼叫了 25 次，面板下方會顯示目前的呼叫次數。
記憶化：算過的就記下來
改法很簡單：準備一個陣列 memo，memo[n] 存 fib(n) 的答案，還沒算過的放 -1。
- 進入
fib(n)時，先查memo[n]：已經算過就直接回傳 - 沒算過才真的去算，算完存進
memo[n]再回傳
這種「遞迴＋查表」的寫法叫記憶化（memoization），也叫由上而下（top-down）的動態規劃：從大問題往下拆，遇到算過的子問題就不再往下。
每個 fib(k) 只會真正計算一次，所以 fib(n) 只需要 O(n) 次計算，用 O(n) 的空間存答案。
記憶化：重複的呼叫消失了
遞迴樹先沿著左邊一路往下到 fib(1)、fib(0)，回程時把答案一格一格填進 memo。之後右邊的 fib(4)、fib(3)… 一查表就回傳，不再長出子樹。總共只呼叫 11 次（直接遞迴是 25 次）。
什麼問題適合用動態規劃
「動態規劃」這個名字是 Richard Bellman 在 1950 年代取的，當時他在 RAND 研究多階段的決策問題。 這裡的 programming 指的是「規劃、排出計畫表」，不是寫程式；把子問題的答案一格一格填進表格，正是這個意思。
一個問題適合用動態規劃，通常有兩個特徵：
| 特徵 | 意思 | 費氏數列 |
|---|---|---|
| 重疊子問題（overlapping subproblems） | 拆出來的子問題會重複出現 | fib(4)、fib(3) 被算很多次 |
| 最佳子結構（optimal substructure） | 大問題的答案可以由子問題的答案組合出來 | fib(n) = fib(n - 1) + fib(n - 2) |
和前面學過的方法比較：
- 分治法（第 07 課的合併排序）也拆子問題，但子問題不重疊（左半、右半各排一次），所以不需要記下來
- 貪婪法（第 20 課）每一步只選一個方向、不回頭；動態規劃把每個選擇的結果都算出來再比較，所以能處理貪婪法會失敗的問題
想一想：重疊子問題與記憶化
下面的程式會印出什麼？
calls = 0
def fib(n):
global calls
calls += 1
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
fib(6)
print(calls)
費氏數列加上記憶化之後，算 fib(n) 的時間複雜度是多少？
合併排序也把問題拆成子問題，為什麼它不需要記憶化？
表格法：從最小的子問題往上填
記憶化是從大問題往下拆。另一種寫法反過來：從最小的子問題開始，依序把表格填滿，填到要的那一格就是答案。 這叫表格法（tabulation），也叫由下而上（bottom-up）的動態規劃，不需要遞迴。
用爬樓梯當例子：每次可以跨 1 階或 2 階，走到第 n 階有幾種走法？
設計動態規劃通常有四個步驟：
- 定義狀態：
dp[i]是走到第 i 階的走法數 - 寫出轉移式：走到第 i 階的最後一步，不是從 i - 1 階跨 1 階，就是從 i - 2 階跨 2 階，所以
dp[i] = dp[i - 1] + dp[i - 2] - 設定初始值：
dp[0] = 1（站在地面，什麼都不做也算一種）、dp[1] = 1 - 決定計算順序：
dp[i]要用到比較小的格子，所以 i 由小到大算
轉移式和費氏數列一模一樣，只是初始值不同。
爬樓梯：dp 陣列一格一格填
每一輪 dp[i] 都由它左邊的兩格相加。表格從左往右填，用到的格子一定已經算好。走到第 7 階共有 21 種走法。
方格路徑：二維的表格
一個 4 列 5 行的方格，從左上角走到右下角，每一步只能往右或往下，有幾條不同的路？其中第 1 列第 2 行（從 0 算起）是障礙物，不能經過。
- 狀態：
dp[i][j]是從左上角走到格子 (i, j) 的路徑數 - 轉移式：走進 (i, j) 的最後一步，不是從上面 (i - 1, j) 下來，就是從左邊 (i, j - 1) 過來，所以
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；障礙物的格子是 0 - 初始值：起點
dp[0][0] = 1；第 0 列沒有上面、第 0 行沒有左邊，那一項當作 0 - 計算順序：一列一列、由左到右，算 (i, j) 時上面和左邊都已經算好
沒有障礙物時答案是 35（7 步裡選 3 步往下）；有了障礙物，經過它的路都不能算。
方格路徑：一列一列填表
框起來的是正在計算的格子，它的值等於上面一格加左邊一格。第 1 列第 2 行是障礙物，一直是 0，所以它右邊和下面的格子少了從它過來的路。右下角的答案是 17。
找零錢：最少要幾枚
第 20 課看到，面額 1、3、4 要湊 6 元時，貪婪法先拿 4，結果用了 3 枚，最少其實是 2 枚（3 + 3）。動態規劃不先做決定，而是把每種可能都比較：
- 狀態：
dp[x]是湊出 x 元最少要幾枚 - 轉移式：湊 x 元的最後一枚可能是 1、3 或 4 元。如果最後一枚是 c 元，前面就要先湊好 x - c 元，所以
dp[x] = min(dp[x - c] + 1)，對每個 c ≤ x 取最小 - 初始值：
dp[0] = 0；其他先設成一個不可能的大數（這裡用 amount + 1，因為最多也只要 amount 枚 1 元），表示「還湊不出來」 - 計算順序：x 由小到大
另外用 used[x] 記下湊 x 元時最後用的那枚硬幣。算完之後從 used[6] 開始往回走，就能還原出實際用了哪些硬幣，而不只是知道枚數。
時間複雜度是 O(金額 × 面額種類數)。
找零錢的動態規劃
每個 x 都試三種「最後一枚」，▲ x-c 指出它要參考的格子。看 x = 6：用 1 元要 dp[5] + 1 = 3 枚，用 3 元只要 dp[3] + 1 = 2 枚，用 4 元要 dp[2] + 1 = 3 枚，所以 dp[6] = 2。最後從 used[6] = 3 往回走，還原出 3 + 3。
想一想：填表格
3 列 3 行、沒有障礙物的方格，從左上角走到右下角（只能往右或往下）有幾條路？
面額 1、5、6，用本課的動態規劃湊 10 元，最少要幾枚？（貪婪法會用 6 + 1 + 1 + 1 + 1 共 5 枚）
找零錢的表格法裡，為什麼 x 要由小到大算？
實作：一次可以跨 1、2 或 3 階
把爬樓梯改成每次可以跨 1、2 或 3 階。請完成 dp[i] 的轉移式，算出 4、6、10 階各有幾種走法。
重點整理
- 動態規劃：每個子問題只算一次，把答案記下來；適用於有重疊子問題和最佳子結構的問題
- 記憶化（由上而下）：遞迴＋查表；表格法（由下而上）：從最小的子問題往上填，不用遞迴
- 費氏數列直接遞迴的呼叫次數隨 n 指數成長，動態規劃只要 O(n)
- 設計四步驟：定義狀態、寫出轉移式、設定初始值、決定計算順序
- 爬樓梯
dp[i] = dp[i - 1] + dp[i - 2]；方格路徑dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；找零dp[x] = min(dp[x - c] + 1) - 另外記下每一格「是從哪個選擇來的」，就能還原出最佳解的實際做法
下一課：動態規劃經典問題。0/1 背包、最長共同子序列、編輯距離，都是用二維表格解的問題。