62. 不同路径

力扣打卡:62. 不同路径

解题思路

检查了那么多遍,用自顶向下的已知不通过,就觉得很迷,后来发现,我在 planB 调用的是暴力递归的 planA 方法,太不小心了

  • 暴力递归
  • 当前节点 [m,n] 到 节点 finish 的总路径和就是 right + bottom 路径和
  • 终止条件 basecase 是在 finish 节点时,返回1,超出索引范围 返回0
  • (优化终止条件:可以检查发现,当在最后一行或者最后一列时,只能往右或者往下走,直接返回1即可)

自顶向下

  • 暴力递归的方法最重要!找出转移的状态,也就是当前的状态和子问题的状态的联系关系

  • 写出了暴力递归,加一个状态储存和状态判断就是自顶向下的动态规划了

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[] rc = {m,n};
        // return planA(rc, 0, 0);
        int[][] dp = new int[m][n];
        for(int i=0; i<dp.length; i++){ // 将数组初始化为一个与题目的变量没有关系的-1
            Arrays.fill(dp[i],-1);
        }
        return planB(dp, rc, 0, 0);
    }
    // 分析:
    // 每次只能走下或者走右,定义一个函数,能够得到每个节点到最终点的路径条数
    // 那么状态转移的过程就是当前的节点 返回的是  2 + count( up ) + count( right )
    // 终止的条件是 如果是产出索引返回,那么返回相应的数值0
    // 如果是finish 的节点或者是finish的上节点或者左节点,那么返回1,因为无论如何所有的节点都必须经过这两个节点才能到达finish
    public int planA(int[] rc, int m, int n){ 
        if(m==rc[0]-1 || n==rc[1]-1) return 1; // 在最后一行或者最后一列只能往右走或者是往下走,所以只能右一条路径
        if(m==rc[0] || n==rc[1]) return 0; // 如果超出索引返回,那么返回0

        int down = planA(rc, m+1, n); // 下边的节点到finish的路径条数
        int right = planA(rc, m, n+1); // 右边的节点到finish的路径条数


        return down+right; // 本身就可以往下和往右走,那么也就是 下 右 的条数进行返回

    }
        // 暴力递归写出来了,那么自顶向下的方式也就是多增加一个记录,判断的过程

    public int planB(int[][] dp, int[] rc, int m, int n){ 
        if(m==rc[0]-1 || n==rc[1]-1) return 1; // 在最后一行肯定只能往右走,在最后一列肯定只能往下走,所以只会有一条路径
        if(m==rc[0] || n==rc[1]) return 0; // 如果超出索引返回,那么返回0
        
        if(dp[m][n] != -1) return dp[m][n]; // 检查是否已经计算过了

        int down = planB(dp, rc, m+1, n); // 下边的节点到finish的路径条数
        int right = planB(dp, rc, m, n+1); // 右边的节点到finish的路径条数,不要写成了planA了,检查了那么久发现还是通不过

        dp[m][n] = down + right;
        return dp[m][n]; // 本身就可以往下和往右走,那么也就是 下 右 的条数进行返回

    }
    
}
上一篇:840--矩阵中的幻方(找规律)


下一篇:greenplum-执行SQL创建Slice&Gang 学习计划。