算法21 Unique Paths II

这是之前一个算法的升级版本。
之前题目：一个机器人在 m × n 的网格中的左上角（在下面示意图中标记 'Start' 的位置）。
在同一时间点中，机器人只能向下或者向右走。机器人的目标是右下角（用 'Finish' 标记的位置）
问：有多少种不同的路线？
本题题目：现在如果我们给栅格中加入了障碍，那会有多少种不同的路径呢？
在栅格中障碍标记为 1，空格标记为 0。

例如，
下面是在 3 × 3 的栅格正中央有一个障碍的情况：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
不同的路径数是 2。
注意： m 和 n 都 <= 100.
思路：
这题和上一题不同在于有了障碍，所以关键在于对障碍的分析：
① 遇到障碍把障碍的值设为 0 代表无法到达这一点
② 初始化第一行第一列的时候若遇到障碍，把障碍后面的数也都置为 0（因为后面永远无法到达）

代码：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    //若传入值为空，则返回0
    if(obstacleGrid.length == 0) return 0;
    //得到行列的长度
    int rows = obstacleGrid.length;
    int cols = obstacleGrid[0].length;
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
            //若为1则设为 0
            if(obstacleGrid[i][j] == 1)
                obstacleGrid[i][j] = 0;
                //把第一个点设为1
            else if(i == 0 && j == 0)
                obstacleGrid[i][j] = 1;
                //第一行第一列中若有存在障碍，则它后面的都为0（不可达到）
            else if(i == 0)
                obstacleGrid[i][j] = obstacleGrid[i][j - 1] * 1;
            else if(j == 0)
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] * 1;
            else
                //当前位置 = 左边 + 上面
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
        }
    }
    return obstacleGrid[rows - 1][cols - 1];
}

复杂度：空间复杂度O(n),时间复杂度O(raw*cols)