繼第 6 天的「53. Maximum Subarray」，今天來解 64 這題！還沒看過第 6 天或再之前天數的朋友，歡迎也去看看~

今天這題有點前一天的進階版的感覺，那話不多說，我們開始吧！

這篇總共提供了兩種解法，為了說明都有附上模擬步驟。如果想要直接看程式碼，請搜尋關鍵字「程式碼」以快速移動！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/minimum-path-sum/

演算法與資料結構

• Path
• Dynamic Programming (DP)
• Greedy

題意

給予一個大小為 m * n 的非整數二維陣列，找出其中一個從左上到右下並最小和的路徑。這個路徑只能往右和往下移動。

範例

1. 二維陣列解法

分析 DP 的子問題

二維陣列要尋找子問題，就可以先取一個 2*2 的二維陣列，接著再將同樣的邏輯拓展到整個二維陣列。

講解時以這個陣列為例：

+---+---+
| 1 | 2 |
+---+---+
| 3 | 4 |
+---+---+

可以得知最小和 7 的路徑是

1 -> 2 -> 4 

如何走訪的路徑，就再把子問題限縮到 1*1 ，只有一個元素的二維陣列。

邏輯

根據題意，因此可以幫每一個位置訂下規則

+---+
| 1 |
+---+

首先，單一位置的基本規則為：

1. 若 上 和 左 都沒有值，意味處於角落，則加總值為 自己
2. 若 上 沒有值，意味處於第一列，則加總值為 左 和 自己
3. 若 左 沒有值，意味處於第一欄，則加總值為 上 和 自己
4. 若 上 和 左 都有值，則取兩者較小值和 自己 加總

擴張到 1 * 2 的陣列

+---+---+
| 1 | 2 |
+---+---+

步驟 1 [0][0]

若 上 和 左 都沒有值，意味處於角落，則加總值為 自己

執行後為：

+---+---+
| 1 | 2 |
+---+---+

步驟 1 [0][1]

若 上 沒有值，意味處於第一欄，則加總值為 上 和 自己

執行後為：

+---+---+
| 1 | 3 |
+---+---+

答案

3

擴張到 2 * 2 的陣列

+---+---+
| 1 | 2 |
+---+---+
| 3 | 4 |
+---+---+

Step 1 [0][0] 的結果

+---+---+
| 1 | 2 |
+---+---+
| 3 | 4 |
+---+---+

Step 2 [0][1] 的結果

+---+---+
| 1 | 3 |
+---+---+
| 3 | 4 |
+---+---+

Step 3 [1][0] 的結果

+---+---+
| 1 | 3 |
+---+---+
| 4 | 4 |
+---+---+

Step 3 [1][1] 的結果

+---+---+
| 1 | 3 |
+---+---+
| 4 | 7 |
+---+---+

最終結果

回傳最右下角的值即為結果

7

路徑為

1 -> 2 -> 4

程式碼

開始執行核心 routine 之前

1. 如果二維陣列或 grid 數量不足，則直接回傳
2. 複製一個可變更的二維陣列用來暫存走訪過程的值

接下來只要把列和欄都走訪，套上 DP 分析後得出的邏輯即可：

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        guard !grid.isEmpty && !grid[0].isEmpty else { return 0 }
        var grid = grid 
        for row in 0..<grid.count {
            for column in 0..<grid[0].count {
                if row == 0 && column == 0 {
                    continue 
                } else if row == 0 {
                    grid[row][column] += grid[row][column - 1]
                } else if column == 0 {
                    grid[row][column] += grid[row - 1][column]
                } else {
                    grid[row][column] += min(grid[row - 1][column], grid[row][column - 1])
                }
            }
        }
        return grid[grid.count - 1][grid[0].count - 1]
    }
}

複雜度分析

根據題意，二維陣列大小為 m * n

執行結果

• Runtime: 47 ms (Beats 77.59%)
• Memory: 14.3 MB (Beats 88.79%)

2. 一維陣列解法 / 貪婪

從第一個解法看得出來用來運算的二維陣列，其實只有當前的前一個 row 有用途，在那之前的 rows 其實都不需要被暫存

分析 DP 的子問題

將暫存的資料結構改為陣列之後，邏輯則為

1. 若 上 和 左 都沒有值，意味處於角落，將 自己 推入暫存陣列
2. 若 上 沒有值，意味處於第一列，則將 暫存陣列 的 左 和 自己 推入暫存陣列
3. 若 左 沒有值，意味處於第一欄，則加總值為 暫存陣列 的 當前欄 和 自己 更新到 暫存陣列 的 當前 欄
4. 若 上 和 左 都有值，則取「暫存陣列 的 當前 欄」和「暫存陣列 的 左 欄」中的較小值和 自己 加總後更新到 暫存陣列 的 當前 欄

補充說明，在開始運算之前

• 「暫存陣列 的 當前 欄」- 以二維陣列的暫存的角度來看就是前一列的結果
• 「暫存陣列 的 左 欄」- 以二維陣列的暫存的角度來看就是 當列左欄 和 min(當列左 2 欄, 前一列左欄) 加總後的結果

接著來分步驟來觀察：

  +---+---+
  | 1 | 2 |
  +---+---+
  | 3 | 4 |
  +---+---+

+
|
+

    v
  +---+---+
> | 1 | 2 |
  +---+---+
  | 3 | 4 |
  +---+---+


+---+
| 1 |
+---+

        v
  +---+---+
> | 1 | 2 |
  +---+---+
  | 3 | 4 |
  +---+---+

+---+---+
| 1 | 3 | // 1 + 2 = 3
+---+---+

    v
  +---+---+
  | 1 | 2 |
  +---+---+
> | 3 | 4 |
  +---+---+

+---+---+
| 4 | 3 | // 1 + 3 = 4
+---+---+

        v
  +---+---+
  | 1 | 2 |
  +---+---+
> | 3 | 4 |
  +---+---+

+---+---+
| 4 | 7 | // min(3, 4) + 4 = 3 + 4 = 7 (答)
+---+---+ // 這邊的 3 是指前一個暫存陣列 [1] 的 3 ，並非 grid[1][0] 的 3

程式碼

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        guard !grid.isEmpty && !grid[0].isEmpty else { return 0 }
        var sums = [Int]()

        for row in 0..<grid.count {
            for column in 0..<grid[0].count {
                if row == 0 && column == 0 {
                    sums.append(grid[row][column])
                } else if row == 0 {
                    sums.append(grid[row][column] + sums[column - 1])
                } else if column == 0 {
                    sums[column] += grid[row][column]
                } else {
                    sums[column] = grid[row][column] + min(sums[column - 1], sums[column])
                }
            }
        }
        return sums.last!
    }
}

複雜度分析

根據題意，二維陣列大小為 m * n

執行結果

• Runtime: 46 ms (Beats 82.76%)
• Memory: 14.3 MB (Beats 72.41%)

解法比較

理論空間複雜度雖然減少了一個維度，但是對 LeetCode 的測試案例，就執行結果來說記憶體用量很可惜的沒有差別。

結語

很久沒這樣畫圖解釋邏輯了，如果有什麼問題和回饋歡迎留言一起討論，

今天就到這裡，明天見！