前面幾天我們做了幾道題，熟悉了一維數列形式的1-D DP題型，在這類問題中狀態是單一的(例如爬樓梯問題的第i階、扒手問題的第i間房…等等)。

接下來，讓我們更進一步來看看類似的二維矩陣遞迴題型，這也是我們第一次遇到2-D以上的動態規劃問題。

目錄

🟨求不同路徑總數I

本題取自 Leetcode 62. Unique Paths

題目

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down


Constraints:

1 <= m, n <= 100

分析

還記得在day4的文章中我們練習過的爬樓梯題目嗎？在該題中，題目規定「要在一步之內走到某一階，只能從前一階或者前兩階」。可觀察到包括這個規則、要從某一個位置走至最終的位置，以及求可能的路徑總數，這些都和本題有共同之處。

分治法

本題要求只能向右或者向下走到下一個格子

若我們討論「走到某一格的走法數量」：

• 前一步必定是從左，或者從上
• 且來自兩個方向的路徑不可能是同一種路徑
• 所以只要問這兩格各自的走法數量，再加總即可。

設計狀態、找出轉移式與最小問題

狀態：定義paths(i,j)為走至第(i,j)格的路徑數量

轉移式：根據分治法，任何路徑都只能來自左方或者上方一格，因此

paths(i,j) = paths(i-1,j) + paths(i,j-1)

邊界條件：分析題目後可知：

• 當所求格子是最左一格，就不會從左邊走來。
• 同樣的道理，當所求格子是最上一格，就不會從上面走來。
• 此外，若詢問paths(0,0)，因為是出發點，路徑總數為1(注意不是0)

因此，若我們計算實際的走法數，會發現在最左一行的任何一格，以及最上一列的任何一格，都僅有一種走法。(就是從出發格直直走)

從矩陣類的問題開始，我們會遇到逐漸複雜化的邊界條件，讀者可以多注意在兩個策略的實作當中如何去處理邊界條件。

母問題所求：求paths(m-1, n-1)

實作

Top-Down DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def paths(i,j):
            if i==0 or j==0: return 1  # 最左or最上一格 
            return paths(i-1, j) + paths(i, j-1)

        return paths(m-1, n-1)

注意：在遞迴過程中，子問題會被重複問到(每一格可以往右或者往下走)，因此需要使用@cache或者手刻快取來記錄答案。

Bottom-Up DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 產生一個 m x n 矩陣來記錄。path(i,j)答案 => dp[i][j]
        dp = [[0 for _ in range(n)] for _ in range(m)] 
        # 由上往下、由左往右迭代計算
        for i in range(m):           # y軸: 0 ~ m-1
            for j in range(n):       # x軸: 0 ~ n-1
                if i == 0 or j == 0: # 最上/最左一格 
                    dp[i][j] = 1 
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

可以發現，當需要紀錄的狀態不只一個(例如本題是一個2-D的DP)，則bottom-up我們所規劃的儲存答案陣列，以及計算的順序就會變得比較複雜。

設計計算順序時要注意：後算的問題，會採用先算的問題的答案

以本題來說，我們規劃了一個m x n的矩陣，用來記錄paths(i,j) = dp[i][j]，至於計算的順序，則是從上到下計算每一列(for i)，並且每一列從左到右計算(for j)。

因為從上到下計算，所以計算時，用到「上面一格」的答案時已經算好了，直接從dp取用即可。同理，因為從左到右計算，所以用到「左邊一格」的答案時已經算好了，直接從dp取用即可。

不過，上面所示範的答案，還有(儲存空間上)優化的空間！

觀察計算順序以及轉移式之後，我們會發現：

• 計算時只會用到上面一列，而不會用到更上面的列數，且順序是由上往下計算
• 計算時只會用到左邊一格，而不會用到更上左邊的格數，且順序是由左往右計算

換言之，並不需要占用m x n的空間，而只需要保留(目前所計算到的)最後一列的答案。

優化後的bottom-up dp如以下範例：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        dp = [1 for _ in range(n)]     # 最上一列：均只有1種路徑
        # 由上往下、由左往右迭代計算
        for _ in range(1,m):           # y軸: 1 ~ m-1
            for j in range(1,n):       # x軸: 1 ~ n-1
                dp[j] = dp[j] + dp[j-1]
        
        return dp[-1]

概念是：只用1-D的List來記錄某一行的答案，並且每計算一格，就直接覆蓋掉其上方一格的答案(因為用不到了)。

轉移式dp[j] = dp[j] + dp[j-1]看起來會覺得有點奇怪，這是因為我們直接挪用上一列的答案陣列，繼續記錄下一列的答案。

等號後面的dp[j]代表的是上面一格的路徑數，而dp[j-1]代表的是左邊一格的路徑數

這個技巧又稱為在原址(inplace)動態規劃，應對空間要求比較刁鑽的題目時，大多都靠這招就可以解決。

複雜度分析

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(m x n)，計算複雜度 = O(1)

因此時間複雜度 = O(m x n)

空間複雜度

因為需要記住每題子問題的答案，空間複雜度 = 狀態數 = O(m x n)

如果使用原址的bottom-up，則空間複雜度 = O(n)

數學公式解

本題有數學公式解，其實這個問題也出現在中學的排列組合問題中。排組給出的解法是這樣的：

無論何種路徑，要從(0,0)走到(m-1,n-1)，必定需要往下走m-1步，且往右走n-1步。

例如：測資Example2：m = 3, n = 2，必須往下2步且往右1步。則3種走法可以分別寫作：

↓ ↓ →

↓ → ↓

→ ↓ ↓

換言之，原問題等價於求m-1個A物與n-1個B物的線形排列數，即C(m+n-2, m-1)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m+n-2, m-1)

當然，公式解只適用於簡單的模板題，一旦題目稍有變化(例如地圖上挖個不能走的洞)便無法使用。

不過這種「OOO問題其實等價於XXX問題」的思維可謂許多演算法問題(或者廣泛的說是數學問題)的突破口，值得我們學習。

---

🟨最小路徑總和

本題取自 Leetcode 64. Minimum Path Sum

題目

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12
 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

分析

迷宮的走法和上一題(Leetcode 62.)相同，只能往右或者往下。

上一題要求所有不同的路徑總數，而本題則是在迷宮中填入數字，要求這些路徑之中，該路徑所經過的數字總和最小的。

分治法

經過上一題的練習，不難找到這個子問題：

對於迷宮中的某一格grid[i][j]，從起點grid[0][0]走到這格，最小數字總和的路徑是多少？

因為走到這格，只能從左邊一格grid[i][j-1]或者上面一格grid[i-1][j]走來，所以只要從這兩格的子問題答案中求較小值，再加上grid[i][j]這格本身的數值，即為子問題的答案。

題目所求則為最右下角那格grid[m-1][n-1]的子問題答案。

設計狀態、找出轉移式與最小問題

狀態：minSum(i,j)

從起點grid[0][0]走到grid[i][j]的路徑中最小數字總和

轉移式：

minSum(i,j) = grid[i][j] + min( minSum(i-1,j), minSum(i,j-1) )

最小問題(邊界條件)：

當子問題問到最左一行時，即minSum(i,0)，此時不需要考慮「左邊」的minSum(i,-1)，因為左邊已經沒有格子了。同理，當子問題問到最上一列的minSum(0,j)時，不需要考慮「上面」的minSum(-1,j)，因為上面已經沒有格子了。

可以多觀察在以下的實作中如何處理邊界條件。

題目所求(母問題)：minSum(m-1,n-1)

Top-Down DP

注意：在遞迴過程中，子問題會被重複問到(每一格可以往右或者往下走)，因此需要使用@cache或者手刻快取來記錄答案。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def minSum(i,j):
            # 出發點
            if i==0 and j==0: return grid[0][0]
            
            # 最左一行或者最上一列，往前一格遞迴時
            # 透過回答無限大，來讓min自動排除這個路徑
            if i==-1 or j==-1: return float('inf')
            
            # 狀態轉移式
            return grid[i][j] + min(
                minSum(i,j-1) , minSum(i-1,j)
            )
        # 回答母問題答案 (最右下角那格)
        return minSum(len(grid)-1, len(grid[0])-1)

Bottom-Up DP

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0]) # 矩陣的高與寬
        # 建立記錄答案用的空矩陣
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # 出發點
        dp[0][0] = grid[0][0]
        # 最上一列，只能從左邊走來
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j-1]
        for i in range(1, m):
            # 每列的最左一格，只能從上面走來
            dp[i][0] = grid[i][0] + dp[i-1][0]

            for j in range(1, n):
                # 狀態轉移式
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        # 返回母問題答案：最右下角那格
        return dp[-1][-1]

和前一題類似的做法，若要更加節省空間也可以做inplace的處理：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # grid 高、寬
        m, n = len(grid), len(grid[0]) 
        # 記錄「已計算過的最後一列」答案用的陣列
        ## 出發點
        dp = [grid[0][0]]
        ## 最上面一列
        for j in range(1, n): 
            dp.append(grid[0][j] + dp[j-1])

        # 由上往下計算每一列
        for i in range(1, m):
            # 最左邊一格
            dp[0] = grid[i][0] + dp[0]
            # 由左往右計算每一格
            for j in range(1, n):
                # 轉移式
                dp[j] = grid[i][j] + min(dp[j-1], dp[j])
        
        # 母問題答案(最右下一格)
        return dp[-1]

和前一題類似，因為計算子問題答案只需要左邊一格和上面一格，且我們由上至下逐列計算，因此，當計算完某格之後，其上方一格的答案已經不需要了。所以我們只需要反覆用一個1-D的陣列來記錄2-D的「每一行」答案。

這樣做的優點是最省空間，但轉移式「乍看之下」會跟分治法推導的不同，需要注意：

dp[j] = grid[i][j] + min(dp[j-1], dp[j])

• 等號前的dp[j]，計算並紀錄子問題答案minSum(i,j)
• 等號後的dp[j-1]是剛計算過的minSum(i,j-1)
• 等號後的dp[j]是還沒被覆蓋掉的「上一行的答案」，所以其實代表的是minSum(i-1,j)

這樣分析之後就能看出，其實和前面分治法所推導的轉移式仍是相同的。

複雜度分析

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數為O(m x n)，計算複雜度為O(1)，因此總複雜度為O(m x n)

空間複雜度

記錄所有子問題答案的空間複雜度為O(m x n)。

若採用 inplace Bottom-Up 的寫法則可以降到O(n)。

---

🟨求不同路徑總數II

本題取自 Leetcode 63. Unique Paths II

題目

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.

分析

同樣作為第一題(Leetcode 62.)的變化題，本題在迷宮加入了障礙物，走迷宮的規則不變(只能往右、下)，並且求左上走到右下、不遇到障礙物的路徑總數。

分治法

我們仍可以問和第一題相同的子問題：對於某一格，走到該格的總路徑數為多少？

• 如果這格為障礙物，則為0(因為任何路徑都不能有障礙物)
• 如果這格不為障礙物，則和第一題完全相同，為左邊一格的答案+上面一格的答案。

設計狀態、找出轉移式與最小問題

狀態：定義paths(i,j) = 走到第(i,j)格的路徑總數

轉移式：

• 這格有障礙物：grid[i][j] == 1，則：

  paths(i,j) = 0

• 這格沒有障礙物：grid[i][j] == 0，則：

  paths(i,j) = paths(i-1,j) + paths(i,j-1)

邊界條件：和第一題相同：

• 出發點paths(0, 0)：若沒有障礙物則= 1，若有障礙物則= 0
• 路徑不會超出左邊、上面的邊界(i、j不能 < 0)

實作

Top-Down DP

注意：在遞迴過程中，子問題會被重複問到(每一格可以往右或者往下走)，因此需要使用@cache或者手刻快取來記錄答案。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @cache
        def paths(i,j):
            # 有障礙物
            if obstacleGrid[i][j]: return 0
            # 出發點
            if i==0 and j==0: return 1
            # 最上一列
            if i==0: return paths(i,j-1)
            # 最左一行
            if j==0: return paths(i-1,j)
            # 一般情況
            return paths(i,j-1) + paths(i-1,j)
        # 回答母問題答案 paths(m-1, n-1)
        return paths(len(obstacleGrid)-1, len(obstacleGrid[0])-1)

Bottom-Up DP

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                # 有障礙物
                if obstacleGrid[i][j]==1: dp[i][j] = 0
                # 無障礙物
                ## 出發點
                elif i==0 and j==0: dp[i][j] = 1
                ## 最上一列
                elif i==0:  dp[i][j] = dp[i][j-1]
                ## 最左一行
                elif j==0: dp[i][j] = dp[i-1][j]
                ## 其他情況
                else: dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # 回答母問題答案 dp[m-1][n-1]
        return dp[-1][-1]

若要更加節省空間也可以做inplace的處理：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0 for _ in range(n)]
        for i in range(m):
            for j in range(n):
                # 有障礙物
                if obstacleGrid[i][j]: dp[j] = 0
                # 無障礙物
                ## 出發點
                elif i==0 and j==0: dp[j] = 1
                ## 最上一列
                elif i==0: dp[j] = dp[j-1]
                ## 最左一行
                elif j==0: pass
                ## 其他情況
                else: dp[j] += dp[j-1]
        # 回答最右下角 dp[m-1][n-1]
        return dp[-1]

複雜度分析

值得一提的是，儘管大部分的矩陣題資料緊密，Bottom-Up通常算得比較快，但本題在障礙物很多的情況下，反而是Top-Down算得比較快。

箇中差異在於，Top-Down的遞迴函式有early return的性質，每當遇到障礙物，直接返回0，並不會繼續往起點遞迴，去問前一格的子問題。

由於Bottom-Up必定計算所有的狀態，當障礙物很多時，Top-Down這種剪枝(pruning)的效果就發揮出來，省掉了很多不必要的計算。

以這題來說，若某格由於前後都被障礙物堵死，沒有任何「合法」的路徑能通過，此時Bottom-Up仍然會遍歷計算每一格，但是Bottom-Up在遇到其中一端的障礙物時就直接early return掉(放棄這條路徑)，並不會計算到這一格的狀態。

這也正是大多數圖論的DP問題使用Top-Down策略都能較容易解決的原因。當題目的網絡越複雜，節點的規則、條件判斷越來越多時，Top-Down就能發揮剪枝的優勢；反而Bottom-Up會苦於無法掌握計算順序，或者把資源都拿去計算根本用不到的節點形成無形的浪費。

不過本題只是簡單的有/無障礙物判斷，所以兩個策略的效能表現其實差不多。

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數為O(m x n)，計算複雜度為O(1)，因此總複雜度為O(m x n)

空間複雜度

記錄所有子問題答案的空間複雜度為O(m x n)。

若採用 inplace Bottom-Up 的寫法則可以降到O(n)。

---

矩陣題型都大同小異，重點在於掌握合法路徑的規則來推導轉移式。

以上為Day06的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天我們會接著再看幾題矩陣的題型。