链接
题目：
思路：dp
定义备忘录memo[i][j] 为从左上角出发，到当前位置的路径最小和；
状态转移：[i][j] 位置只会由 [i-1][j] 和[i][j-1] 两个路径而来，所以只需要在这两个路径的值中取最小，再加上grid[i][j]当前大小，就等于memo[i][j]；
即memo[i][j]=Math.min( dp(grid,i-1,j),dp(grid,i,j-1) ) + grid[i][j]
class Solution {
int[][] memo;
public int minPathSum(int[][] grid) {
//
int n=grid.length;
int m=grid[0].length;
// memo定义，从顶层到memo[i][j]的最小和
memo=new int[n][m];
for(int i=0;i<n;i++){
Arrays.fill(memo[i],-1);
}
return dp(grid,n-1,m-1);
}
int dp(int[][] grid,int i,int j){
if(i<0 || j<0){
return Integer.MAX_VALUE;
}
//base case
if(i==0 && j==0){
return grid[0][0];
}
// 重叠子问题
if(memo[i][j]!=-1){
return memo[i][j];
}
memo[i][j]=Math.min(dp(grid,i-1,j),dp(grid,i,j-1)) +grid[i][j] ;
return memo[i][j];
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89188.html
