江门住房和城乡建设部网站,网站建设预算,wordpress集团网站,做网站后台需要什么LCR 099. 最小路径和
解题思路
采用动态规划的思路每次搜索都是向上或者向左进行搜索dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值。同时(i,j)到(i - 1,j - 1)有两种方法#xff0c;所以一定存在重叠子问题设置备忘录Memo存储dp过程中所有…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];}
}
