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.
Note: You can only move either down or right at any point in time.
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
题意:
给定一个二维矩阵, 找出一条从左上角到右下角的path,能使得这条path经过的所有数字相加之和最小
思路:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
二维dp
1 4 5 2 ? dp[i][j] 6
初始化,
dp[0][0] = grid[0][0]
是否需要预处理第一个row: dp[0][j], 因为矩阵中间的dp[i][j]既可能来自上方,也可能来自左方。所以先预处理仅来自左方的path数字之和 dp[0][j] = dp[0][j-1] + grid[0][j]
是否需要预处理第一个col:dp[i][0],因为矩阵中间的dp[i][j]既可能来自上方,也可能来自左方。 所以先预处理仅来自上方的path数字之和 dp[i][0] = dp[i-1][0] + grid[i][0]
转移方程,
因为矩阵中间的dp[i][j]既可能来自上方,也可能来自左方, 要使得path的数字之和最小,必须比较上方和左方的结果哪个更小,再相加到当前的grid[i][j]上
dp[i][j] = min( dp[i-1][j], dp[j-1][i] ) + grid[i][j]
代码:
class Solution {
public int minPathSum(int[][] grid) {
// init
int[][] dp = new int[grid.length ][ grid[0].length];
dp[0][0] = grid[0][0];
for(int i = 1; i< grid.length; i++){
dp[i][0] = grid[i][0] + dp[i-1][0] ;
} for(int j = 1; j< grid[0].length; j++){
dp[0][j] = grid[0][j] + dp[0][j-1] ;
}
// func
for(int i = 1; i< grid.length; i++){
for(int j = 1; j< grid[0].length; j++){
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[grid.length-1 ][ grid[0].length-1];
}
}