[LeetCode] Minimum Path Sum
文章目录
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.
DP
Time Complexity
O(mn)
Space Complexity
O(mn)
思路
Use dp, matrix here means the sum of the the min sum of all numbers along it's path to matrixi. The base case is the first row and first col of the matrix. There are two ways to go to matrixi, from top or left. sumi = gridi + Math.min(sumi - 1, sumi).
代码
public int minPathSum(int[][] grid) {
//corner case
if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
int rows = grid.length, cols = grid[0].length;
int[][] sum = new int[rows][cols];
sum[0][0] = grid[0][0];
for(int i = 1; i < rows; i++){
sum[i][0] = sum[i - 1][0] + grid[i][0];
}
for(int j = 1; j < cols; j++){
sum[0][j] = sum[0][j - 1] + grid[0][j];
}
for(int i = 1; i < rows; i++){
for(int j = 1; j < cols; j++){
sum[i][j] = Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
}
}
return sum[rows - 1][cols - 1];
}
优化
Time Complexity
O(mn)
Space Complexity
O(1)
思路
Because we only care about the value from top and left, so we can just change the value of grid to make it in place.
代码
public int minPathSum(int[][] grid) {
//corner case
if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return -1;
int rows = grid.length, cols = grid[0].length;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(i == 0 && j == 0) grid[i][j] = grid[i][j];
else if(i == 0 && j != 0){
grid[i][j] += grid[i][j - 1];
}else if(i != 0 && j == 0){
grid[i][j] += grid[i - 1][j];
}else{
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
}
return grid[rows - 1][cols - 1];
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论