一次看懂遞迴 (Recursion) 的思維模式（五）

動態規劃（Dynamic Programming）

這是遞迴系列文的最後一篇，如果讀者對遞迴還不太熟悉，可以先看前幾篇

1. 遞迴基礎
2. Divide and Conquer
3. Backtracking
4. Combination and Permutation

這篇來和大家聊聊動態規劃（Dynamic Programming），這是個令滿多初學者害怕的題目，因為觀念本身稍微難懂，加上題型千變萬化，有時候真的很不容易。不過本章就是想用最簡單的題型來帶大家初步瞭解這個令人生畏的演算法，期望你看完後，就能對動態規劃最核心的精神有初步理解，將來遇到稍難的題目，也能試著挑戰看看。

動態規劃的核心精神，跟遞迴其實是非常類似，但有一個不同點

1. 大問題可以拆成小問題
2. 小問題解決，可以幫助解決大問題
3. 小問題之間時常重複

第三點就是動態規劃的關鍵，如果小問題都不重複，那我們也只能老老實實的全部搜索一次，前面四篇介紹的題目，幾乎都屬於這種狀況。但如果小問題會重複的話，我們就可以用更聰明的方式，去重複利用已知的答案，而不是傻傻的一直重算浪費時間。接下來，就讓我們來看看最經典的例子：

費氏數列（Fibonacci Sequence）

如果還記得，本系列的第一篇，我們最後留下了一個給讀者自己思考的問題，就是費氏數列。這是個非常有名的數列，其數列定義是：

前兩個元素都是 1，後面每一個元素則都是前兩個元素相加，如下

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

我們的題目是，請寫出一個 function，可以告訴我第 x 個費氏數列的數字是什麼，先來幫大家回憶一下思路：

1. 大問題：找到費氏數列中，第 X 個數的數值
2. 小問題1：找到費氏數列中，第 X-1 個數的數值
3. 小問題2：找到費氏數列中，第 X-2 個數的數值
4. 大小問題的關聯式：fibonacci(x) = fibonacci(x-1) + fibonacci(x-2)
5. 最小問題：第 1 個與第 2 個數的數值

def fibonacci(x):
    if x == 1 or x == 2:
        return 1
    return fibonacci(x-1) + fibonacci(x-2)

看似非常簡單，但其實暗藏危機，讓我們圖解一下，上面的解法發生了什麼事（以 X = 5為例，並將 fibonacci 簡寫成 fab)

當我們要算 fibonacci(5) 的時候，我們需要先算 fibonacci(4) 與 fibonacci(3) 再相加，而算 fibonacci(4) 的時候又需要先算 fibonacci(3) 與 fibonacci(2) ，依此類推，最後就是上面這張圖。而我們會發現圖中有些東西重複出現了很多次，例如 fab(3) 出現了兩次，而 fab(2) 出現了三次。

如果把他當成樹來看，幾乎每個節點都有兩個孩子，最終時間複雜度會變成 O(2^N)。大家可以用電腦跑跑看，大約在 X=30～40 左右就會開始感覺到程式運算非常緩慢。

那我們如何解決這個問題呢！答案其實非常的簡單，就是把運算過得答案用 Hash Table 記錄下來即可。往後只要看到重複出現的數字，就重複使用記錄過的答案，而不要繼續遞迴下去，所以你的關係圖其實就會變成下面這樣，如果一樣把他想成一顆樹，那這次除了最底下那層（最小問題）有兩個孩子，其餘皆為一個，因此時間複雜度可以降到 O(N)。

概念講完，一樣來寫程式，我們使用 dp = {}當作記錄器，記錄曾經出現過的答案，假如記錄過就直接使用即可，沒出現過則需要遞迴計算，之後將結果其記錄下來。

以上面兩張圖為例的話，就是當左側的 fab(3) 已經計算過，我就會記錄 dp[3] = 3，如此一來，當右側又需要詢問 fab(3) 的時候，就可以從 dp[3] 直接拿取答案，而不用再繼續重新往下遞迴一次 fab(2) 與 fab(1)，以下是範例程式碼。

這次，同樣計算 X = 40 就可以輕鬆秒殺了，就算 X = 100 也是小菜一碟。實際上，因為我們已經讓時間複雜度從可怕的 O(2^N)，變成 O(N) 了，這是非常巨大的進步。

註：如果你曾經聽說過遞迴會造成效率非常差，並以費氏數量當作例子，很可能他只是忘記加上一個記錄器而已，只要加上去就沒問題了。

接下來，我們來看一另一個，稍難一點的經典例子

找零錢

這是 Leetcode 上面的題目，叫做 Coin Change 2，題目是這樣的

我們手上有幾種不同面額的零錢：Coins = [1, 2, 5]
我想付一定的金額：Amount = 5
請問我有幾種不同支付方式（同一種 Coin可以重複使用）

一樣，我們先肉眼找找看答案，總共有以下四種

1. 5
2. 2+2+1
3. 2+1+1+1
4. 1+1+1+1+1

如果你有看上一篇的 Combination 的話。你可能可以想到一個很簡單的解法，就是把 [1, 2, 5] （且元素可以重複使用）的所有可能 Combination 都列出來，那只要挑出有幾組相加爲 5，就是答案了。

以下，我們採用每個 Coin 逐個判斷”使用”與”不使用”的想法來嘗試解決這題，增加一個小條件就是，用過的還可以繼續用，但放棄就不再使用，從下一個開始，詳細規則如下：

1. 方框內的數字代表現在已經選取的 Coins
2. 方框右方數字代表現在考慮繼續使用的 Coin
3. 往左走代表使用此 Coin，且繼續考慮使用
4. 往右走代表不使用此 Coin（所以已經選取的 Coins 保持不便，但考慮的 Coin 改成下一個）

但如果這樣做，當你在 Leetcode 送出答案後，會得到一個 Time Limit Exceeded，意思是演算法超時了。事實上這確實又是一個 O(2^N) 數量級的做法，依照上面的概念，看來我們又需要一個記錄器了。

但，如果你再仔細看一下上圖，也會發現過程中你其實沒有什麼重複的子問題出現，所以也沒辦法套用我們上面說的記錄法。所以到底該怎麼辦呢？

這就是動態規劃（Dynamic Programming）問題的難點了，往往我們的第一步：如何拆解問題，就是整個演算法的關鍵。如果一開始的拆解方式不對，就做不出來了。

所以讓我們重新想想，這題還能怎麼拆。觀察一下，這題與前面最大的差別其實在於：他只需要你告訴我總共有幾種付錢方式，而沒有要你把付錢方式的所有排列都找出來，這是很重要的差異。所以我們其實不需要真的去列舉所有排列可能性，只需要知道他的加總是多少即可。然後這次讓我們練習用扣的，也就是說我們一開始剩餘總額 (Remain) 是 5，現在對於每一個 Coin，我們一樣選擇”使用”或”不使用”，規則如下：

1. 假如選擇使用它，Remain 就會減去 Coin 的值，且此 Coin 還可以使用
2. 假如選擇不使用他，那就不會再用到他了，未來都從下一個開始考慮起
3. 整個過程中，如果 Remain 歸零，就是一種可能的答案，如果 Remain 變負的，就不可能是答案，也不需要繼續下去。

所以我們的遞迴改成如下圖所示：

並且我們把取得答案的想法也稍微改一下，由於我們要的是總共有幾種可能，於是這次不再是在底層蒐集答案，而是將答案往上回傳並加總，思維如下：

1. 大問題的答案，等於兩個小問題的答案相加（e.g. 假如左邊孩子有 3 種可能，右邊孩子有 5 種可能，那我的答案就是 8 種可能，因為左右是兩種完全不同的情境）
2. 最底層的孩子，如果剛好 Remain 剩 0，就會回傳 1（代表 1 種答案），如果 Remain < 0，則回傳 0 （代表 0 種答案），如果可用的 Coin 已經用完，但 Remain 還沒剩 0，當然也是回傳 0。

可以試著先看懂核心概念的程式碼（暫且不考慮記錄問題）：

def helper(self, coins, start, remain):
    if start == len(coins): # 使用的 Coin index 超過 Coins 總數
        return 0
    if remain < 0: # 剩餘值變成負的，不可能為答案
        return 0
    if remain == 0: # 剩餘剛好為 0，找到一組答案
        return 1
    left_count = helper(coins, start, remain-coins[start]) #用此 Coin 
    right_count = helper(coins, start + 1, remain) #不用此 Coin
    return left_count + right_count

但，這樣的遞迴方式，跟上面直接處理 Combination 有什麼差異呢？如果仔細看我們上圖的方框，會發現終於有重複的東西出現了！紫色那層與藍色那層都出現了一樣的東西，如下：

這代表，兩種狀況，其實只要算一次就好了！

但讀者可能還是會很好奇，那這樣實際上到底省下多少時間呢？看起來重複的也不多，我怎麼確定這樣比直接展開所有可能的 Combination 好多少呢？這邊來教大家分析動態規劃問題時間複雜度的做法：

定義狀態

以上圖來說，每個分支出來的東西，就是一個狀態（也就是前幾篇說的”小問題”們），換句話說，方框中間的數字與右邊的數字構成一個狀態。由於相同的狀態，可以透過記錄，不需再次處理。所以最終我們的時間複雜度，就取決於有可能出現多少種不重複的狀態。以一個稍大一點的例子來舉例：

Amount = 5000
Coins = [3,5,7,8,9,10]

狀態定義 1：所有可能的組合

若我們的狀態定義就是各種組合，例如 (Coins: [3, 5, 7]、Consider Coin: 7) 是一種狀態，(Coins: [10, 10, 10]、Consider Coin: 10)，又是另一種狀態，這種狀態有多少種呢？確實不太好估計，但因為數字很大，我們可以隨意概算，以下是筆者自己的估法，沒完全看懂也沒關係，你可以用自己喜歡的方式估算，應該都會發現數量級過大。

Coin 可以重複取用（等於有無限多個），目標 Amount 是 5000，最大面值的硬幣為 10，所以需要選取的硬幣總數，最少也要 500 個。我們套用重複組合的概念，總共 6種硬幣，共取 500個，可能的不同排列法為 H(6, 500) = C(505, 500) = 268318178226，已經很明顯太大了，但實際數字還要遠超過這個很多，因為當我們用面額更小的硬幣，需要的數量就會遠超過 500。

狀態定義 2：餘下的 Remain 與目前考慮第幾個 Coin

這個就簡單多了，因為餘下 Remain 的範圍只可能在 0~5000，而 Coin 總數只有 6，所以所有可能的不重複狀態只有 (5000 + 1) * 6 = 30006。是不是變得非常小。

由此可知，狀態的定義只要選的足夠漂亮，我們就能用與前幾篇的遞迴思維，加上本章提到的記錄狀態技巧來解題了。下面是最終的範例程式碼，給讀者們參考。

如果你能努力看到這邊，非常的棒！以後看到動態規劃的問題，就是想辦法找可能的狀態，並找到狀態之間的關聯性，最後透過記憶來增加效能。找狀態定義方式的時候，儘可能用到最少需要的資訊，才比較有辦法讓狀態互相之間有重複，也才能真正加速。

很多人會害怕動態規劃，是因為覺得狀態定義方式很抽象，我數學也不是很好，那怎麼才能知道哪個才是對的？是要通靈嗎？

但其實，無他，惟手熟爾，而通常面試來說，一般小公司只會出現 2~3 種基礎型，你多看到幾次其實就能辨認了，而整個 Leetcode 全部頂多也就七八種大類型，只要願意花時間下去練一定是可以全數掌握的，不用太害怕，不會給你無止境的一直變出完全想像不到的東西。

至於高等級的程式競賽（例如 Codeforce, Facebook Hacker Cup, Google Code Jam…)，確實動態規劃題可以千變萬化，出題者為了求新求變，接受各路高手挑戰，會結合各種其他演算法與資料結構，玩出各種花式狀態定義法，定義完之後還可能有各種花式的優化方式，這只能在各種高難度題型中經年累月的不斷出征累積經驗，才有可能掌握的了。但這… 就留給競賽選手們去煩惱就好，凡人無需涉入過深。

遞迴的部分就到這邊結束，但最後額外補充一下，大部分的動態規劃題其實都有兩種寫法，分別是

1. Top-Down
2. Bottom-Up

Top-Down 的寫法就是本篇介紹的，通常會以遞迴為主，思路比較是從最大問題開始思考，並一路往下遞迴小問題。但還有另一種 Bottom-Up 的寫法，則是從最小問題出發，然後慢慢往上處理大問題，這種寫法通常以迴圈為主，且用 Bottom-Up 的寫法時，通常不需要再額外考慮記錄器的問題，因為我們一開始就已經在記錄了，可參考下面程式碼：

Fibonacci

Coin Change 2

其實大多數時候在處理態規劃問題時，Bottom-Up 的寫法是比較推薦的，因為會讓程式碼更簡潔，遇到難度更高的問題時也更容易思考如何優化。但即便如此，Top-Down 的思維方式有時候也會派上用場的，當狀態不一定會真的被走遍時，往往可以增加不少效率（筆者就曾在 Leetcode 比賽中遇過只有 Top-Down 寫法才能過的題目）。所以讀者可以試著一起學習兩種寫法，也體會一下兩者的異同。

最後稍微再講一個小細節，Coin Change 2 這題的 Bottom-Up 還有更簡潔的寫法，其實他是另一個非常知名的動態規劃題型的一種，叫做無限背包問題，如果還有興趣深究的朋友們可以試著查查看噢。未來如果有機會也會和大家來好好專題介紹動態規劃這個博大精深的演算法。

這系列到這邊結束，感謝大家收看！

系列連結

1. 遞迴基礎思維
2. 分治法 Divide And Conquer 與兩大排序法
3. 回溯法 Backtracking
4. 排列與組合（Permutation & Combination)
5. 基礎動態規劃（Dynamic Programming）