动态规划：06不同路径II

动态规划：06不同路径II

63. 不同路径 II

本题相较于动态规划：05不同路径就是有了障碍

五部曲

1. 确定dp数组含义：到达第i，j位置的路径条数为d[i][j]

2. 确定递归公式：d[i][j]=d[i-1][j]+d[i][j-1]

   本位置有障碍物就是0

3. dp数组初始化：dp[0][j] = 1,dp[i][0] = 1

   有障碍物后面的就都是0

4. 遍历顺序：从左到右，从上到下

   我们的初始值是在最上面和最左面

5. debug：打印dp数组

代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        //如果在起点或终点出现了障碍，直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                //该位置没有障碍物，才可以到达
                if(obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        //debug->打印dp数组
        // System.out.println(Arrays.deepToString(dp));

        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结

本题是动态规划：05不同路径的障碍版，整体思路大体一致。

但就算是做过62.不同路径，在做本题也会有感觉遇到障碍无从下手。

其实只要考虑到，遇到障碍dp[i][j]保持0就可以了。

也有一些小细节，例如：初始化的部分，很容易忽略了障碍之后应该都是0的情况。