Given m x n grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum. You can only move right or down.
Input: [[1,3,1],[1,5,1],[4,2,1]] → Output: 7Input: [[1,2,3],[4,5,6]] → Output: 12
DP in-place: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j].
- Initialize first row and column as prefix sums.
- For i,j from 1 to m,n: dp[i][j] = min(from_above, from_left) + grid[i][j].
- Return dp[m-1][n-1].
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
return grid[m-1][n-1];
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(1) in-place