动态规划Day02

62.不同路径

力扣题目链接(opens new window)

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

看到题目的第一想法

? ? ? ? dp ，看到达网格位置有多少种不同的路径

看到代码随想录之后的想法

? ? ? ? 动规五部曲，很快的写出解题思路

? ? ? ? 1确定dp数组以及对应下标的含义

? ? ? ? dp[i][j] 到达i j 位置有多少中不同的路径

? ? ? ? 2确定递推公式

? ? ? ? dp[i][j] = dp[i-1][j]+dp[i][j-1]

????????3dp数组初始化

? ? ? ? 需要把第一行和第一列都初始化，都为1

? ? ? ? 4确定遍历顺序

? ? ? ? 从上往下，从前往后

? ? ? ? 5手动推导dp数组

? ? ? ? 6打印dp数组

? ? ? ? 打印dp[m-1][n-1]

自己实现过程中遇到的困难

? ? ? ? 注意初始化

class Solution {
    public int uniquePaths(int m, int n) {
        //确定dp数组，和下标的含义
        //dp[m-1][n-1] 代表到达需要的路径总数
        //确定递推公式
        // dp[i][j]=dp[i-1][j]+dp[i][j-1]
        //dp数组如何初始化
        //dp[0][0]=1 dp[0][1]=1 dp[0][2]=2 ...dp[1][0]=1
        //确定遍历顺序
        //双重for循环 i j
        //打印dp数组
        int[][] paths = new int[m][n];
        for(int i=0;i<m;i++){
            //这里应该是1  之前看成i了
            paths[i][0]=1;
        }
        for(int j=0;j<n;j++){
            paths[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                paths[i][j]=paths[i-1][j]+paths[i][j-1];
            }
        }
        return paths[m-1][n-1];
    }
}

63. 不同路径 II

力扣题目链接(opens new window)

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

看到题目的第一想法

? ? ? ? dp ，看到达网格位置有多少种不同的路径

看到代码随想录之后的想法

? ? ? ? 动规五部曲，很快的写出解题思路

? ? ? ? 1确定dp数组以及对应下标的含义

? ? ? ? dp[i][j] 到达i j 位置有多少中不同的路径

? ? ? ? 2确定递推公式

? ? ? ? 若为障碍物 dp[i][j]则置为0

? ? ? ? dp[i][j] = dp[i-1][j]+dp[i][j-1]

????????3dp数组初始化

? ? ? ? 需要把第一行和第一列都初始化，都为1，若遇到障碍物则都为0

? ? ? ? 4确定遍历顺序

? ? ? ? 从上往下，从前往后

? ? ? ? 5手动推导dp数组

? ? ? ? 6打印dp数组

? ? ? ? 打印dp[m-1][n-1]

自己实现过程中遇到的困难

? ? ? ? 没有注意到只能向下和向右

? ? ? ? 注意这个for循环的写法 j<obstacleGrid[0].length&&obstacleGrid[0][j]!=1

?????????for(int j=0;j<obstacleGrid[0].length&&obstacleGrid[0][j]!=1;j++){
? ? ? ? ? ? dp[0][j]=1;? ?
? ? ? ? }

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //卡哥纠错:注意题意只能向右和向下走
        //确定dp数组下标的含义
        //到达这个位置所需要的路径数目，如果有阻碍，置为0
        //确定递推公式
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        //确定遍历顺序
        //i j
        //dp数组初始化
        // 边界为1 如果有阻碍为0
        //打印dp数组
        //return dp[m][n]
        if(obstacleGrid[0][0]==1&&obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1]==1){
            return 0;
        }
        //如果每一行全为1 or 某一列全为1 则无法满足 
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        /*for(int i=0;i<obstacleGrid.length;i++){
            if(obstacleGrid[i][0]==1){
                dp[i][0]=0;
            }else{
                dp[i][0]=dp[i-1][0];
            }
        }
        for(int j=0;j<obstacleGrid[0].length;j++){
            if(obstacleGrid[0][j]==1){
                dp[0][j]=0;
            }else{
                dp[0][j]=dp[0][j-1];
            }
        }*/
        //卡哥思路，若初始化有障碍，后面都为0，我的写法复杂了点
        for(int i=0;i<obstacleGrid.length&&obstacleGrid[i][0]!=1;i++){
            dp[i][0]=1;
            
        }
        for(int j=0;j<obstacleGrid[0].length&&obstacleGrid[0][j]!=1;j++){
            dp[0][j]=1;
            
        }
        for(int i=1;i<obstacleGrid.length;i++){
            for(int j=1;j<obstacleGrid[0].length;j++){
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}