【动态规划】 LCR 099. 最小路径和

LCR 099. 最小路径和

解题思路

• 采用动态规划的思路
• 每次搜索都是向上或者向左进行搜索
• dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值。
• 同时(i,j)到(i - 1,j - 1)有两种方法，所以一定存在重叠子问题
• 设置备忘录Memo存储dp过程中所有重叠子问题的解

class Solution {int[][] memo;// 备忘录public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;memo = new int[m][n];for(int[] row:memo){Arrays.fill(row,-1);}return dp(grid,grid.length - 1,grid[0].length - 1);}int dp(int[][] grid,int i,int j){if(i == 0 && j == 0){return grid[0][0];}if(i < 0 || j < 0){return Integer.MAX_VALUE;}// 查找备忘录 有没有子问题的结果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];}
}