leetcode 63. 不同路径 II

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

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

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

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

和上一题类似，只是在路径中添加了障碍物，把有障碍物的位置设置为0，表示没有路径可以达到该点， 此外对于第一行和第一列只要出现了障碍物，其后面或者其下面的点均不可到达；

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int i, j, x=obstacleGrid.size(), y=obstacleGrid[0].size();
        vector<vector<int>> dp(x, vector<int>(y, 1));
        bool f1=false, f2=false;
        for(i=0; i<x; i++){
            for(j=0; j<y; j++){
                if(obstacleGrid[0][j]==1) f1=true;
                if(obstacleGrid[i][0]==1) f2=true;
                if(obstacleGrid[i][j]==1) dp[i][j]=0;
                if((f1 && i==0) || (f2 && j==0)) dp[i][j]=0;
            }
        }
        for(i=1; i<x; i++)
            for(j=1; j<y; j++)
                if(dp[i][j]) dp[i][j] = dp[i][j-1] + dp[i-1][j];
        return dp[x-1][y-1];
    }
};

这种算法简洁一些，没有上面繁杂的判断语句； 思维很棒！ 在起点之前添加一个点；初始化条件是dp[0][1]或者dp[1][0]都是可行的；与上面不同的是，每一个点的初始值是0，并且是从第0行第0列开始遍历的

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int i, j, x=obstacleGrid.size(), y=obstacleGrid[0].size();
        vector<vector<int>> dp(x+1, vector<int>(y+1, 0));
        dp[0][1]=1;
        for(i=1; i<=x; i++)
            for(j=1; j<=y; j++)
                if(!obstacleGrid[i-1][j-1]) dp[i][j] = dp[i][j-1] + dp[i-1][j];
        return dp[x][y];
    }
};