【动态规划】 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];
    }
}