給定一個
m x n的非負整數網格，找從左上角到右下角的路徑，使路徑上數字總和最小。每次只能往右或往下移動。
Example:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 (路徑 1->3->1->1->1)
Intuition
TIP
經典網格 DP：每個格子的最小路徑和等於上方或左方較小者加上當前格子的值。
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])- 第一行只能從左邊來，第一列只能從上面來
- 可以直接在原陣列上修改，省空間
Approaches
1. 2D DP (in-place) — O(m * n) / O(1)
- Idea: 直接在
grid上累加，grid[i][j]加上從上方或左方來的較小值。 - Time:
O(m * n) - Space:
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 — O(m * n) / O(n)
- Idea: 用一維陣列滾動更新，
dp[j]保留上一行的值（即「上方」），dp[j-1]是當前行已更新的值（即「左方」）。 - Time:
O(m * n) - Space:
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(上, 左) - Key trick: 與 62 題結構相同但目標不同（路徑數 vs 最小和）；原地修改可達 O(1) 空間