82. Minimum Path Sum
Moving only right or down from the top-left to the bottom-right of grid, minimise the sum of the numbers on your path.
Example 1
Input:
grid = [[1,3,1],[1,5,1],[4,2,1]]Output:
7Explanation: Path 1 → 3 → 1 → 1 → 1.
Example 2
Input:
grid = [[1,2,3],[4,5,6]]Output:
12Hint 1
best(r, c) = grid[r][c] + min(best(r−1, c), best(r, c−1)).
Approach 1: 2-D DP
Fill the grid of best sums.
⏱ Time O(m · n)💾 Space O(m · n)
Approach 2: Rolling row ✅
One row of state.
⏱ Time O(m · n)💾 Space O(n)
Reference solution for Rolling row (time O(m · n), space O(n)). Each solution passes every test in all four languages.
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for r in range(m):
for c in range(n):
left = dp[c - 1] if c > 0 else float('inf')
dp[c] = grid[r][c] + min(dp[c], left) # from above or from the left
return dp[-1]class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
int left = c > 0 ? dp[c - 1] : Integer.MAX_VALUE;
dp[c] = grid[r][c] + Math.min(dp[c], left); // above or left
}
return dp[n - 1];
}
}class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
int left = c > 0 ? dp[c - 1] : INT_MAX;
dp[c] = grid[r][c] + min(dp[c], left); // above or left
}
return dp[n - 1];
}
};function minPathSum(grid) {
const m = grid.length, n = grid[0].length, dp = new Array(n).fill(Infinity);
dp[0] = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
dp[c] = grid[r][c] + Math.min(dp[c], c > 0 ? dp[c - 1] : Infinity); // above or left
return dp[n - 1];
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
Watch the core idea of this problem step by step. Change the input and press Visualize.
Explained in the lesson Dynamic Programming (2-D).
Run your code to see results here.