LeetCode-63. 不同路径 II

缺乏、安全感 2024-03-26 17:28 77阅读 0赞

题目来源  
[63. 不同路径 II][63. _ II]

### 递归 ###

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int row = obstacleGrid.length-1;
            int col = obstacleGrid[0].length-1;
            return process(row,col,0,0,obstacleGrid);
        }
    
        private int process(int row ,int col,int i,int j,int[][] obstacleGrid){
        
            if(i>row || j>col){
        
                return 0;
            }
            if(obstacleGrid[i][j]==1){
        
                return 0;
            }
            if(i == row && j==col){
        
                return 1;
            }
            return process(row,col,i+1,j,obstacleGrid) + process(row,col,i,j+1,obstacleGrid);
        }
    }

![在这里插入图片描述][668ebfd9932744a1adcfdbe43fa06959.png]

### 动态规划 ###

动规五部曲：

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]\[j\] ：表示从（0 ，0）出发，到(i, j) 有dp\[i\]\[j\]条不同的路径。

*  2.确定递推公式

dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\]。

因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

dp[i][j] = obstacleGrid[i][j]==0?dp[i-1][j]+dp[i][j-1]:0;

*  3.dp数组如何初始化

因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp\[i\]\[0\]一定为1，dp\[0\]\[j\]也同理。  
但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp\[i\]\[0\]应该还是初始值0。  
![在这里插入图片描述][c836e6bb45f24d158738d0da54e45143.png]

for(int i = 0;i<row && obstacleGrid[i][0]==0;i++){
        
                dp[i][0] = 1;
            }
            for(int j = 0;j<col && obstacleGrid[0][j]==0;j++){
        
                dp[0][j] = 1;
            }

注意代码里for循环的终止条件，一旦遇到obstacleGrid\[i\]\[0\] == 1的情况就停止dp\[i\]\[0\]的赋值1的操作，dp\[0\]\[j\]同理

*  4.确定遍历顺序

从递归公式dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\] 中可以看出，一定是从左到右一层一层遍历，这样保证推导dp\[i\]\[j\]的时候，dp\[i - 1\]\[j\] 和 dp\[i\]\[j - 1\]一定是有数值。

for(int i = 1;i<row;i++){
        
                for(int j = 1;j<col;j++){
        
                    dp[i][j] = obstacleGrid[i][j]==0?dp[i-1][j]+dp[i][j-1]:0;
                }
            }

*  5.举例推导dp数组  
    ![在这里插入图片描述][5aaf4a6d6eb14f538546f2c209e214a0.png]  
    对应的dp table 如图：

![在这里插入图片描述][03c8db172d074943bedd6cb6bd34f05a.png]  
完整代码

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int row = obstacleGrid.length;
            int col = obstacleGrid[0].length;
            int[][] dp = new int[row][col];
            for(int i = 0;i<row && obstacleGrid[i][0]==0;i++){
        
                dp[i][0] = 1;
            }
            for(int j = 0;j<col && obstacleGrid[0][j]==0;j++){
        
                dp[0][j] = 1;
            }
            for(int i = 1;i<row;i++){
        
                for(int j = 1;j<col;j++){
        
                    dp[i][j] = obstacleGrid[i][j]==0?dp[i-1][j]+dp[i][j-1]:0;
                }
            }
            return dp[row-1][col-1];
        }
    }

![在这里插入图片描述][a0edb322d6f3440283c9c9ac43fce02d.png]

[63. _ II]: https://leetcode.cn/problems/unique-paths-ii/
[668ebfd9932744a1adcfdbe43fa06959.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/496d178e1dda49f98567f120c289f23e.png
[c836e6bb45f24d158738d0da54e45143.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/20bede54de6d49a6887a1d421773963b.png
[5aaf4a6d6eb14f538546f2c209e214a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d242072119614ea89b081bb37147dfc3.png
[03c8db172d074943bedd6cb6bd34f05a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4583f4f7187c4ce0a47be7eb990f61ce.png
[a0edb322d6f3440283c9c9ac43fce02d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/72d57e0c512648e4839e29fc892e57cf.png