[数据结构与算法]64. 最小路径和 | 动态规划 |暴力递归 | 自顶向下

力扣打卡:64. 最小路径和

解题思路

• 还是分析 暴力递归 的方法,然后再写出 自顶向下 的分析流程

• 分析 每个节点 要做的事情是什么,也就是分析出了 状态转移方程

• 状态转移方程 : 当前状态和子问题的结果有什么联系和关联

• 定义暴力递归的函数就认为这个函数可以得到需要的结果,对于子问题同样适合的需要的结果

• 只要将暴力递归写出来了,那么最后自顶向下的动态规划不就多了一个 检查 和 记录 的过程

最重要的流程还是当前的要做什么,和子问题的关联是什么,也就是状态转移的过程是什么

1. 最终的 basecase 是什么,遇到了无解的子问题该怎么做

2. 将暴力递归写出来了就可以了,重要的是分析状态转移方程 以及 定义暴力递归的函数时,就默认这个函数可以得到需要的结果

3. 写暴力递归时,不要想着任何的优化,否则因为对动态规划的不熟悉,就会出现逻辑混乱的情况,也就是参数不知道怎么使用的情况

注意返回的值,索引越界的时候返回的是 Integer.MAX_VALUE

代码

class Solution {
    public int minPathSum(int[][] grid) {
        // return planA(grid, 0, 0);

        int[][] memo = new int[grid.length][grid[0].length];
        for(int i=0; i<memo.length; i++) Arrays.fill(memo[i],-1); // 将备忘录的数字重置为与题目无关的数据,方便判断
        return planB(memo, grid, 0, 0);
    }

    // 看到这种题目，肯定是动态规划的题目
    // 首先先写出暴力递归的解法
    // 对于每一个节点，只能往下走和往右走两条路，此时选择最小的一条路返回即可,这个也就是状态转移方程
    public int planA(int[][] grid, int m, int n){
        if(m==grid.length || n==grid[0].length) return Integer.MAX_VALUE; // 索引越界时,返回的时最大值,因为此时求的时最小值
        if(m==grid.length-1 && n==grid[0].length-1) return grid[m][n]; // 当所在的节点时finish节点,返回finish节点值

        int bottom = planA(grid, m+1, n); // 得到下边路径的最小值
        int right = planA(grid, m, n+1); // 得到右边路径最小值

        int val = Math.min(bottom, right) + grid[m][n]; // 得到下边和右边的最小值的较小值,并且加上当前的值

        return val;
    }

    // 写出了暴力递归的方式,那么自顶向下的方式也就是多了检查的步骤和记录的步骤
    public int planB(int[][] memo, int[][] grid, int m, int n){
        if(m==grid.length || n==grid[0].length) return Integer.MAX_VALUE; // 索引越界,此时因为求的最小值,那么不可到达就标记为整数最大值
        if(m==grid.length-1 && n==grid[0].length-1) return grid[m][n]; // 索引到了finish节点,返回finish节点的值
        if(memo[m][n] != -1)  return memo[m][n]; // 检查此时的节点是否已经计算过,如果计算过直接返回

        int bottom = planB(memo, grid, m+1, n);
        int right = planB(memo, grid, m, n+1);

        int val = Math.min(bottom, right) + grid[m][n];

        memo[m][n] = val;

        return memo[m][n];
    }
}