#64
Minimum Path Sum
Medium 2D grid DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Move only right or down from the top-left to the bottom-right of a grid of non-negative numbers. Minimise the sum of the numbers on the path.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the cheapest right/down path.
Why this works: cost to a cell = its value + the cheaper of above and left.
Example: [[1,3,1],[1,5,1],[4,2,1]]
best path 1→3→1→1→1 = 7✦Hints open one at a time
Best cost to reach a cell = its value + min(best from above, best from left).
The first row and column can only be reached one way.
↗Approach
Fill the grid in place (or a 1D array) using the transition above.
</>Solution (Java)
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) continue;
int up = r > 0 ? grid[r - 1][c] : Integer.MAX_VALUE;
int left = c > 0 ? grid[r][c - 1] : Integer.MAX_VALUE;
grid[r][c] += Math.min(up, left);
}
}
return grid[m - 1][n - 1];
}
}!Common mistake
Using a greedy "go to the cheaper neighbour" walk — it can miss the best path.
Complexity
- Time: O(m·n).
- Space: O(1) when updating the grid in place.
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon