64. Minimum Path Sum

Medium

Description

給定一個 m x n 的非負整數網格，找從左上角到右下角的路徑，使路徑上數字總和最小。每次只能往右或往下移動。

Example:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 (路徑 1->3->1->1->1)

Intuition#

經典網格 DP：每個格子的最小路徑和等於上方或左方較小者加上當前格子的值。

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
第一行只能從左邊來，第一列只能從上面來
可以直接在原陣列上修改，省空間

Approaches#

1: 2D DP（原地修改）#

概念: 直接在 grid 上累加，grid[i][j] 加上從上方或左方來的較小值。
時間複雜度: O(m * n)
空間複雜度: O(1)（原地修改）

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (i == 0 && j == 0) continue
                val fromUp = if (i > 0) grid[i - 1][j] else Int.MAX_VALUE
                val fromLeft = if (j > 0) grid[i][j - 1] else Int.MAX_VALUE
                grid[i][j] += minOf(fromUp, fromLeft)
            }
        }
        return grid[m - 1][n - 1]
    }
}

⭐2: 1D DP#

概念: 用一維陣列滾動更新，dp[j] 保留上一行的值（即「上方」），dp[j-1] 是當前行已更新的值（即「左方」）。
時間複雜度: O(m * n)
空間複雜度: O(n)

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val dp = IntArray(n)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (i == 0 && j == 0) {
                    dp[j] = grid[i][j]
                } else if (i == 0) {
                    dp[j] = dp[j - 1] + grid[i][j]
                } else if (j == 0) {
                    dp[j] = dp[j] + grid[i][j]
                } else {
                    dp[j] = minOf(dp[j], dp[j - 1]) + grid[i][j]
                }
            }
        }
        return dp[n - 1]
    }
}

🔑 Takeaways#

Pattern: 網格型 DP — dp[i][j] = grid[i][j] + min(上, 左)
關鍵技巧: 與 62 題結構相同但目標不同（路徑數 vs 最小和）；原地修改可達 O(1) 空間