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 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

---

承接LeetCode Unique Paths，只是把网格中设置了障碍，第一思路是DFS，如果下一步能走，则递归深入搜索，否则返回。完整代码如下：

class Solution {
public:
    void dfs(vector<vector<int> >& obstacleGrid, int x, int y, int& numPath)
    {
        if (obstacleGrid[x][y] == 1)
            return;
        if (x == obstacleGrid.size() – 1 && y == obstacleGrid[0].size() – 1)
            numPath++;
        else {
            if (y + 1 < obstacleGrid[0].size())
                dfs(obstacleGrid, x, y + 1, numPath);
            if (x + 1 < obstacleGrid.size())
                dfs(obstacleGrid, x + 1, y, numPath);
        }
    }
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)
    {
        int numPath = 0;
        dfs(obstacleGrid, 0, 0, numPath);
        return numPath;
    }
};

但是TLE失败:-(

查题解，恍然大悟，DP解决。设dp[j]为从左上角到obstacleGrid[i][j]共有多少种方案，如果obstacleGrid[i][j]==1，则不可能到达这一点，dp[j]=0；否则，可以从[i][j-1]和[i-1][j]两个点到达[i][j]，即dp[j]=dp[j]+dp[j-1]。因为只用了一个数组保存中间结果，所以右边的dp[j]相当于dp[i-1][j]，dp[j-1]相当于dp[i][j-1]，左边的dp[j]才是dp[i][j]。
$$dp[i][j]=\begin{cases}0\quad\text{if obstacleGrid[i][j]==1}\\dp[i-1][j]+dp[i][j-1]\quad\text{otherwise}\end{cases}$$

完整代码如下：

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

本代码提交AC，用时6MS。