LeetCode 63. Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3×3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
解析：
这个题目是在前一个题目LeetCode 62. Unique Paths上增加了障碍，如果有障碍则表示无法通过。
还是采用动态规划的思想，主要区别在于边界条件的处理。
解法1:
对最左边和最上边的边界分别进行处理，在最上边的边界此时i=0,则有path[i][j]=path[i][j-1];
对于最左边的边界，此时j=0，则有path[i][j]=path[i-1][j]
对于其他位置，判断如果obstacleGrid[i][j]==0,则path[i][j] = path[i-1][j] + path[i][j-1]

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid.size()==0)
            return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector< vector<int> > path(m, vector<int>(n));
        path[0][0] = obstacleGrid[0][0]==1?0:1;
        for(int i=0; i<m;i++)
        {
            for(int j=0; j < n; j++)
            {
                if(i>=1 && j>=1)
                {
                    if(obstacleGrid[i][j]==0)
                        path[i][j] = path[i-1][j] + path[i][j-1];
                    else
                        path[i][j] = 0;
                }else if(i>=1)
                {
                    if(obstacleGrid[i][j]==0)
                        path[i][j] = path[i-1][j];
                    else
                        path[i][j] = 0;
                }else if(j>=1)
                {
                    if(obstacleGrid[i][j]==0)
                        path[i][j] = path[i][j-1];
                    else
                        path[i][j] = 0; 
                }
            }                
        }
        return path[m-1][n-1];
    }
};

运行结果：

解法2:
另一种处理的方式类似于前一个题目的处理，从i=1,j=1开始处理，path的维度为(m+1)*(n+1),最终返回的是path[m][n]，即用path[i+1][j+1]存放实际单元格[i,j]的所有可能路径。因此初始令path[0][1]=1,这样使的path[1][1]为首元素。
关于初始值设置dp[0][1]=1的解释，因为在这里dp[1][1]为起始点，这样如果obatacle[0][0]如果是0，确保dp[1][1]=1,否则dp[1][1]=0，因为dp[1][1]由dp[0][1]或者dp[1][0]得到，所以如果设置dp[1][0]=1也是相同的效果。
具体代码如下：

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

update in 2019.7.31 LeetCode增加了新的testcase，上面代码会出现超过int表示范围的情况，代码更新如下：

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

运行结果：

参考：
https://blog.csdn.net/zhangxiao93/article/details/49582951
https://leetcode.com/problems/unique-paths-ii/discuss/23248/My-C++-Dp-solution-very-simple!</vector</vector</vector</vector</m;i++)></vector