不同路径Ⅱ

题目

具体思路

1. 和第一个的思路相同，但是需要增加判断，也就是在碰到障碍物的情况下的考虑 ；
2. 显然如果将障碍物的出现设置为不增加，那么后续的判断会出现问题，所以我们需要设置为0；

具体实现

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int column = obstacleGrid[0].length;
        int[] res = new int[column + 1];
        res[1] = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 1; j <= column; j++) {
                if (obstacleGrid[i][j - 1] == 0) {
                    res[j] += res[j - 1];
                } else {
                    res[j] = 0;
                }
            }
        }
        return res[column];
    }
}

这里我们给出压缩数组的方式，当前状态的改变取决于：1. 当前的 map 是否是有障碍物，有的话设置为0；2. 否则根据上方的路径以及左侧的路径得到当前的结果。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int column = obstacleGrid[0].length;
        int[][] res = new int[row + 1][column + 1];
        res[0][1] = 1;
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= column; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    res[i][j] = 0;
                } else {
                    res[i][j] = res[i - 1][j] + res[i][j - 1];
                }
            }
        }
        return res[row][column];
    }
}

这里我们给出一个不带压缩数组的形式，保存了所有的中间结果；

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // 1.定义dp数组，i行j列
        vector<vector<int>> dp(obstacleGrid.size() + 1,
                               (vector<int>(obstacleGrid[0].size() + 1, 0)));
        // 3.初始化
        if (obstacleGrid[0][0])
            return 0;
        dp[1][1] = 1;
        for (int i = 1; i <= obstacleGrid.size(); i++) {
            for (int j = 1; j <= obstacleGrid[0].size(); j++) {
                // 2.状态转移方程
                if (i == 1 && j == 1)
                    continue;
                if (obstacleGrid[i - 1][j - 1])
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[obstacleGrid.size()][obstacleGrid[0].size()];
    }
};