前言

我希望可以熟悉DP的思維，剛好看到這篇Medium | Ultimate Guide to Dynamic Programming獲得蠻多的讚，所以打算這篇為基礎做筆記。

在解決Dynamic Programming重要的前提是：

• 耐心: DP問題通常需要花時間來思考，不要急著寫程式
• 熟悉遞迴: DP問題通常可以用遞迴的方式來解決，因此熟悉遞迴是很重要的

Recursion遞迴跟DP的不同

遞歸和動態規劃的主要關聯在於：

• 重疊子問題：如果一個遞歸算法在計算過程中重複解決相同的子問題，可以使用動態規劃來優化。這時，遞歸算法可以轉化為帶備忘錄的遞歸（自頂向下的動態規劃）。
• 最優子結構：如果一個問題的最優解可以由其子問題的最優解構成，那麼可以使用動態規劃來解決這個問題。

有一個很簡單的例子，使用Fibonacci數列來說明這兩個概念。

1
2
3
4
5
6

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

1
2
3
4
5
6
7

def fib(n, memo):
    if n in memo:
        return memo[n]
    if n <= 1: 
        return n 
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

DP 是什麼

再深入討論DP之前，作者有提到不應該立即把任何問題視為"DP問題"

1. 應該要先潈清楚問題是否有需要使用Recursion來解決
2. 然後從Recursion的計算中，承認可能有一些Redundancy，再來考慮是否需要使用DP進行改進與優化。

那我們以Leetcode-62-Unique Paths來看一個DP的例子。

機器人位於一個mxn的網格左上角，機器人只能在向下或向右移動，機器人要到達網格的右下角，有多少種不同的方式？

Step 1 Recursion

最一開始，建議從概述你最純粹、最簡單的遞迴解法開始，這樣可以幫助你更好地理解問題。然而第一步驟通常也是最難的，尤其是當題目最終要求要使用dp進一步優化時。在這個過程至終，需要透過確定問題的本質來制訂作戰計畫。但我知道這聽起來很vague(模糊)，每個問題都是獨一無二的只要做得越多，越能夠學習到如何優雅的解決他們。

可以從上圖看到，要先知道，如果今天n=1或是m=1的情況，也就是上圖灰色地帶，你只能盲目的往右或往下走，這樣你就只有一種走法。當你想走到dp[2,2]時，在只能向右或向下移動的情況下，有兩種方式可以到達dp[2][2]。也就是要麼：

1. 先走到dp[1,2]，然後再走到dp[2,2]，也就是當你走到dp[1,2]的路徑時，基本上要到dp[2,2]的路徑數量也不會改遍了，你就只能往下走
2. 先走到dp[2,1]，然後再走到dp[2,2]，也就是當你走到dp[2,1]的路徑時，基本上要到dp[2,2]的路徑數量也不會改遍了，你就只能往右走

然後神奇的事情發生了，在求任何給定步驟(m, n)的唯一路徑數量時，我們可以通過(m,n)的上一格(m-1,n)和左一格(m,n-1)相加來得到。

這個概念可以用以下程式來實作：

1
2
3
4
5
6
7
8
9
10
11
12

'''
TIME: Exponential
SPACE: O(max(m, n))
'''
class Solution:
    def uniquePaths(self, m, n):
        def helper(m, n):
            # 當 m 或 n 為 1 時，只有一種走法（往右或往下走到底）要麽已經在最下面只要往右走，要麽已經在最右邊只要往下走
            if m == 1 or n == 1: 
                return 1 
            # (m,n) 的路徑是 (m-1,n) 和 (m,n-1) 的路徑數量之和
            return helper(m-1, n) + helper(m, n-1)

儘管到目前為止我們的解決方案效率低下，但是關鍵收穫是我們已經確定遞迴關係，可以理解如何通過適當地引用隔壁的格子來計算當前格子的路徑數量。

這正是我們在解決DP問題時的第一步想要到達的位置 – 最蠢的Recursive。

Step 2 Recursion + Memoization

現在我們需要弄七寵如何利用之前低效的解決方案，把它變成更容易消化的東西，這也是真正開始使用DP的地方，再深入討論之前，我們需要先具體定義一下在哪些條件下我們可以真正開始考慮一個問題是否值得使用DP來解決。

建議當面試的時候，大聲地陳述這兩個條件，如果他們都滿足時我們可以使用DP來解決問題。

首先來看第一個狀況，那就是 overlapping subproblems，這個概念在我們的問題中是很明顯的，因為我們在遞迴過程中多次計算相同的子問題。這就是我們可以使用memoization的地方，我們可以在遞迴過程中保存計算過的子問題的結果，這樣我們就不需要再次計算它們了。這個過程叫做 memoization。

通常情況我們會透過將結果存在數據結構中來實現這一點，然後這個數據結構可以讓我們在未來的O(1)的時間內找到結果(e.g. hash table, dictionary, set)。很幸運的是，從Step1 Recursion到Step 2 +Memoization只需要一點點的改動，我們只需要添加兩個項目：

1. 儲存結果：一個代碼可以儲存所有recursive call的結果
2. 檢查是否為重複子問題: 一個邏輯來檢查這個問題是否已經被解決過了，如果是我們將檢索並使用它，而不是重新計算他

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

'''
TIME: O(m * n)
SPACE: O(m * n) [but limited to max call stack size and susceptible to overflow]
'''
class Solution:
    def uniquePaths(self, m, n):
        # 建立一個資料結構儲存結果
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        def helper(m, n):
            # 檢查是否為重複子問題
            if dp[m][n] != 0:
                return dp[m][n]
            if m == 1 or n == 1: 
                return 1 
            # 儲存結果
            dp[m][n] = helper(m-1, n) + helper(m, n-1)
        return helper(m, n)

說明：

• 上面的程式中，在一開始陣列初始化的地方我們建立了一個mxn的網格，這裡我們使用m+1與n+1是為了避免出現out of bound error
• 添加了中止條件：
  • 檢查如果可以在dp中找到結果，就直接返回結果，這樣就不需要再次計算它們了。
  • 保留原有的，如果m或n是1，那麼就回傳1只有一種走法。
• 如果沒有到達任何一個終止，我們就將遞迴的結果更新到dp裡面

走到這裡，下次在調用 m 和 n 的時候，已經不用在重複計算了！

在這裡你可能會注意到我們在解決方法中引入了額外的空間，你是對的！我們需要承認，需要犧牲一點空間來改善時間，在導致DP解決方案的時候，這種權衡是不費吹灰之力的，而這種方式通常只會按linearly或constant的增加空間複雜度，但是會exponentially的提高時間複雜度！這是你可以強調的。

Step 3 Iteration + Tabulation

當你在面試走到這裡時，通常已經相當不錯了，但是仍然可能存在近一步的優化，這就是我們要討論的地方。如果你完全想不到Step2之後還有哪裡可以改進，然後面試官也已經很開心並滿意你的Step2，那你可以收工了。否則，請繫好安全帶！Because we’re shifting gears once again! XD

在這裡我們將使用Tabulation，而不是Memoization。從根本上來說這兩個方法的目標相同 – 儲存我們以前所做的計算，以便在未來的反覆運算中使用它。

但是，Tabulation涉及將計算儲存在array (通常是2-dimensional array)，而Memoization通常儲存在set, object, dictionary。也因此，Tabluation允許我們能夠在不依賴Recursive的狀況下Iteratively反覆遍歷陣列。

那具體，怎麼使用Iteration + Tabulation呢？可以參考下圖：

1. 我們一樣建立一個二維的空間（為了可以使用iterative），然後我們把所有的初始值都設定為1，因為這些cell中一定有至少1種走法，再慢慢更新就好
2. 然後我們通過往回走（從終點到起點），我們可以計算出所有的cell
3. 因此可以發現dp(m,n)是由右邊和下面的cell來計算的，所以我們可以用下面dp[m+1][n] 與 右邊dp[m][n+1]來計算當前cell的值
4. 根據圖中的例子，我們需要遍歷 m=1~0 以及 n=5~0 也就是藍色cell的部分，來計算出所有的cell

我們經常忘記call stack size的限制，例如我們使用python的遞迴函數，當我們的遞迴深度超過997時，就會出現RecursionError。這就是為什麼在這裡我們使用Tabulation，因為這樣我們就不需要擔心這個問題了。那我們來看以下程式吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

'''
TIME: O(n * m)
SPACE: O(n * m)
'''
class Solution: 
    def uniquePaths(self, m, n): 
        # 我們把所有的初始值都設定為 1 因為這些 cell 中一定有至少1種走法
        dp = [[1 for _ in range(n)] for _ in range(m)]
        # 通過往回走（從終點到起點），我們可以計算出所有的 cell
        # -2 是因為(1)從0開始算 (2)我們不需要計算最下排的cell
        for r in range(len(dp) - 2, -1, -1): 
            # -2 是因為(1)從0開始算 (2)我們不需要計算最右排的cell
            for c in range(len(dp[r] - 2, -1, -1)):
                # 裡用下方 和 右邊的 cell 來計算當前 cell 的值
                dp[r][c] = dp[r+1][c] + dp[r][c+1]
        # 因為是從終點到起點，所以最後返回起點的值
        return dp[0][0]

上面的流程大概會長這樣：

• 首先，最下排也就是m=2的所有cell，以及n=6的所有cell都是1，不需要計算
• 我們需要從m=1, n=5的cell開始計算，然後慢慢往左走，直到m=1, n=0的cell (也就是圖片黃色部份)
• 然後再從m=0, n=5的cell開始計算，然後慢慢往左走，直到m=0, n=0的cell (也就是圖片綠色部份)
• 最後得到的dp[0][0]就是我們的答案

請注意，Step2, Step3 的時間複雜度與空間複雜度是相同的，只是說Step3可以擺脫call stack size的限制。讓你品嘗到自由的滋味。

Step 4 Iteration + Tabulation Optimized

如果你已經在面試中很好的完成前三個步驟，你已經做得很漂亮了，如果要再進一步，就是錦上添花，但是不用因為你無法每次都到達這裡而惱羞成怒。

我們來探討一下我們前幾步驟的解決方案中，可能存在一個機會減少這種空間複雜性（但這點上，時間複雜性已經是最優的了）。這就是我們要討論的地方。如果你發現，我們每次在建立recursive的時候，僅僅會需要下面一格跟右邊一格的cell，那我們是不是我們根本不用建立整個mxn的空間，只需要2個空間就足夠了！這肯定會提高我們的空間複雜度。

具體的感覺如下圖：

• 原本來說上圖的左邊，在我們計算完 m=1 這整排的時候，m=2 這排就沒屁用了。那我們是不是可以利用 m=2 這沒屁用的空間？當然可以！
• 所以我們創建新的dp二維空間表（上圖的右圖），然後m只用2排（m=0~1），每算完一排，就整排往下移動(dp[1]=dp[0])，就可以用新的一排繼續算(dp[0])
• 你會發現我們永遠都在計算m=0這排，因為只要把dp[0]更新到dp[1]就好，有種山不轉水轉的感覺

1
2
3
4
5
6
7
8
9
10
11
12
13

'''
TIME: O(n * m)
SPACE: O(n)
'''
class Solution: 
    def uniquePaths(self, m, n): 
        # 只需要建立一個包含2row的table而不是之前的m
        dp = [[1 for _ in range(n)] for _ in range(2)]
        for r in range(len(dp) - 2, -1, -1): 
            for c in range(len(dp[r] - 2, -1, -1)):
                dp[0][c] = dp[1][c] + dp[0][c+1]    # 只計算dp[0]這排
            dp[1] = dp[0]                           # 山不轉水轉，把計算完的dp[0]更新到dp[1]
        return dp[0][0]

Ref

Medium | Ultimate Guide to Dynamic Programming