1 題目描述


給定一個m x n的矩陣，找到一條從左上角到右下角的最小路徑和。每次只能向右或是向下移動。

2 解法

這題與LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南的題目類似，如果你會做Leetcode-62-Unique Paths，這題也是一樣的概念，只是這題是找最小路徑和。

2.1 Recursive

首先我們很清楚，我們只能往右或是往下走，假設i是row，j是column，

所以我們可以寫出以下的關係式

  • 往右：helper(i, j+1) column + 1
  • 往下：helper(i+1, j) row + 1
  • 然後關係式：min(往右, 往下) + 當前
1
min(helper(i, j+1), helper(i+1, j)) + grid[i][j]

接下來我們來解決最小問題的狀況：

  • 如果只有一行或是一列，直接回傳總和，因為只有一條路可以走
  • 何時知道走到底，當i==rows-1和j==cols-1時，就是走到底了，直接回傳grid[i][j]
1
2
if i == rows-1 and j == cols-1:
    return grid[i][j]

我們就可以開始寫程式了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minPathSum(self, grid: List[List[int]]) -> int:
    def helper(i: int, j: int) -> int:
        # 如果只有一行或是一列
        if row == 1 or column == 1:
            return sum(grid)
        # 走到底（終點）
        if i == row - 1 and j == column - 1:
            return grid[i][j]
        
        # 往右和往下選個最小的
        right, down = float('inf'), float('inf')
        if j < column - 1:
            right = helper(i, j + 1)
        if i < row - 1:
            down = helper(i + 1, j)
        return min(right, down) + grid[i][j]

    row = len(grid)
    column = len(grid[0])
    return helper(0, 0)

2.2 Recursive + Memoization

接下來下一步是為了減少重複運算，我們加入Memoization，這樣就不用一直重複計算了。這裡我們可以用一個dp的list來記錄已經計算過的值，我們可以先建立一個與grid一樣大小的list，然後每次計算過的值就存進去，下次再遇到就直接回傳。

建立與matrix相同大小的dp，該dp紀錄起點走到dp[i][j]的最佳解

1
2
3
row = len(grid)
column = len(grid[0])
dp = [[0]*column for _ in range(row)]

然後設計斷點

  • 如果走到底了，直接回傳grid[i][j]
  • 如果只有一行或是一列，直接回傳總和
  • 如果dp不是0，直接回傳dp已經算過的內容
1
2
3
4
5
6
7
if row == 1 or column == 1:
    return sum(grid)
if dp[i][j] != 0:
    return dp[i][j]
if i == row - 1 and j == column - 1:
    dp[i][j] = grid[i][j]
    return dp[i][j]

那我們就可以開始寫完整的程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def minPathSum2(self, grid: List[List[int]]) -> int:
    def helper(i: int, j: int) -> int:
        # 最小問題
        ## 如果只有一行或是一列
        if row == 1 or column == 1:
            return sum(grid)
        ## 已經算過
        elif dp[i][j] != -1:
            return dp[i][j]
        ## 走到底（終點）
        elif i == row - 1 and j == column - 1:
            dp[i][j] = grid[i][j]
            return dp[i][j]

        right, down = float('inf'), float('inf')
        if j < column - 1:
            right = helper(i, j + 1)
        if i < row - 1:
            down = helper(i + 1, j)
        dp[i][j] = min(right, down) + grid[i][j]
        return dp[i][j]

    row = len(grid)
    column = len(grid[0])
    dp = [[-1 for _ in range(column)] for _ in range(row)]
    helper(0, 0)
    return dp[0][0]

2.3 Iterative + Tabulation

接下來我們使用Iterative就不會因為stack size超過導致出錯。這裡我們可以從終點走到起點，一步步計算出所有cell的最佳解，最終走到起點，回傳dp[0][0]就是答案。

建立一個dp的list，裡面的值是當前的最佳解

1
2
3
row = len(grid)
column = len(grid[0])
dp = [[0 * column] for _ in range(row)]

然後我們從終點慢慢往起點計算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for i in range(row-1, -1, -1):
    for j in range(column-1, -1, -1):
        # 最小問題：走到終點
        if i == row-1 and j == column - 1:
            dp[i][j] = grid[i][j]
        # 如果在最下排
        elif i == row - 1:
            dp[i][j] = grid[i][j] + dp[i][j+1]
        # 如果在最右排 
        elif j == column - 1:
            dp[i][j] = grid[i][j] + dp[i+1][j]
        # 其他狀況，因為我們要走回起點，所以不是往上i+1就是往左j+1
        else:
            dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j])

最後完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def minPathSum3(self, grid: List[List[int]]) -> int:
    row = len(grid)
    column = len(grid[0])
    dp = [[0 * column] for _ in range(row)]
    # 開始找
    for i in range(row-1, -1, -1):
        for j in range(column-1, -1, -1):
            if i == row-1 and j == column - 1:
                dp[i][j] = grid[i][j]
            elif i == row - 1:
                dp[i][j] = grid[i][j] + dp[i][j+1]
            elif j == column - 1:
                dp[i][j] = grid[i][j] + dp[i+1][j]
            else:
                dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j])
    # 回傳
    return dp[0][0]

他還有另一個變化，如果不想要寫這麼多if else可以把dp都塞flout('inf')，並且在第一次塞dp也就是塞終點的時候，在比較min的時候，確保第一次比較的值是0即可。大概要做以下工作：

  • 多擴展一層，這樣for loop的時候i+1跟j+1不會超過邊界
  • 然後塞終點到dp時，要確保第一個比較的值是0也就是dp[row-1][column] = 0
1
2
3
4
row, column = len(grid), len(grid[0])
# 多擴展一層，就不需要做這麼多判斷了
dp = [[float('inf')] * (column + 1) for _ in range(row + 1)]
dp[row-1][column] = 0

for loop從終點開始往起點塞dp

1
2
3
4
for i in range(row-1, -1, -1):
    for j in range(column-1, -1, -1):
        # 塞 dp[終點] 時可以確保 grid[i][j] + min(0, inf) = grid[i][j]
        dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j])

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
def minPathSum3_2(self, grid: List[List[int]]) -> int:
    row, column = len(grid), len(grid[0])
    # 多擴展一層，就不需要做這麼多判斷了
    dp = [[float('inf')] * (column + 1) for _ in range(row + 1)]
    dp[row-1][column] = 0

    # 開始找
    for i in range(row-1, -1, -1):
        for j in range(column-1, -1, -1):
            dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j])
    # 回傳
    return dp[0][0]

2.4 Iterative with Constant Space

最後老樣子，我們能不能讓dp的空間更省，其實當我們計算完一排row時，我們只會用到上一排計算完row的值，上上次的就不會用到了，因此dp的row其實只要兩排就好了。

1
2
3
row, column = len(grid), len(grid[0])
dp = [[float('inf')] * (column+1) for _ in range(2)]   # 只需要兩排
dp[0][column] = 0   # 只有第一次為了紀錄終點到dp 會需要寫成0

但是要注意的是，我們每次走完一排，就要把算完的dp[0]更新到dp[1]並且，dp[0][column]要設定為flout('inf')，這樣下一次才能正確的更新dp[0][j]。

1
2
3
4
5
6
for i in range(row - 1, -1, -1):
    for j in range(column - 1, -1, -1):
        dp[0][j] = grid[i][j] + min(dp[0][j + 1], dp[1][j])
    dp[1] = dp[0]
    dp[0][column] = float('inf')  # 其他狀況，要記得使用inf，才可以抓到替換到下一排的資料
return dp[0][0]

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
def minPathSum4(self, grid: List[List[int]]) -> int:
    row, column = len(grid), len(grid[0])
    dp = [[float('inf')] * (column+1) for _ in range(2)]
    dp[0][column] = 0   # 只有第一次為了紀錄終點到dp 會需要寫成0

    # 開始找
    for i in range(row - 1, -1, -1):
        for j in range(column - 1, -1, -1):
            dp[0][j] = grid[i][j] + min(dp[0][j + 1], dp[1][j])
        dp[1] = dp[0]
        dp[0][column] = float('inf')  # 其他狀況，要記得使用inf，才可以抓到替換到下一排的資料
    return dp[0][0]

3 總結

看到這種matrix要找到最佳路徑有幾個準則：

  • Recursive: min(左邊, 下面)+當前 就可以找到最佳解
  • Interative: 從終點開始往起點找到最佳解