Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.
Constraints:
- 1 <= m <= 200
- 1 <= n <= 200
- 0 <= grid[i][j] <= 100
Examples:
Input: [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path with minimum sum is: 1 -> 3 -> 1 -> 1 -> 1
Solutions
Dynamic Programming
We use dynamic programming to solve this problem. We start by initializing the first row and first column of the grid, where each cell is the sum of the current cell and the cell to its left (for the first row) or top (for the first column). Then, for each remaining cell, we add the minimum of the cell above it and the cell to its left to the current cell. The minimum path sum is stored in the bottom right cell of the grid.
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 1;
i < n;
i++) {
grid[0][i] += grid[0][i-1];
}
for (int i = 1;
i < m;
i++) {
grid[i][0] += grid[i-1][0];
}
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];
}Follow-up:
What if we can move in all four directions (up, down, left, right)?
