[TOC]
一、题目描述
一个机器人位于一个 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. 向下 -> 向下 -> 向右 -> 向右
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题算法
让我们稍稍分析一下这一题，你会发现和62题不同路径几乎完全一样，除了多出一个障碍物。然而就是这个障碍物，使得我们无法讨巧使用求组合数的方法。同样，暴力DFS也已经被证明是超时的。
1. 动态规划
思路：
思路与62题的解法3大体上一致，只是由于题目中多出了障碍物这一点，造成了些许的差异。因此下面有些分析就跳过了，不清楚的建议先看一下62题的题解。
按照题目要求，抵达障碍物处便无法再次移动移动。设输入数组为a，存放各网格路径数的数组为dp。由于存在障碍物，dp第0行和第0列我们也不能像之前那样无脑置为1，因为一旦遇到1，之后所有网格的路径数都为0。
于是我们可以这样初始化dp数组：
同样，由于存在障碍物，遇到障碍物时，显然该网格无法再进行移动，无法为以后的网格路径数做出任何贡献。于是我们有状态转移方程：
代码：
这一题在leetcode上对C++有个坑，int会提示整数加法溢出，所以开辟了一个long类型的dp数组，否则可以直接在obstacleGrid上操作。因而时间复杂度，空间复杂度
。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty() || obstacleGrid[0].empty() || 1 == obstacleGrid[0][0])
return 0;
vector<vector<long>> dp(obstacleGrid.size());
for (auto i = 0; i < obstacleGrid.size(); ++i)
dp[i].resize(obstacleGrid[i].size(), 0);
dp[0][0] = 1;
for (auto j = 1; j < dp[0].size(); ++j)
dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0;
for (auto i = 1; i < dp.size(); ++i)
dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0;
for (auto i = 1; i < dp.size(); ++i)
for (auto j = 1; j < dp[i].size(); ++j)
dp[i][j] = obstacleGrid[i][j] == 0 ? dp[i - 1][j] + dp[i][j - 1] : 0;
return dp.back().back();
}
};
PS1：可以利用滚动数组，将空间复杂度降低到。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty() || obstacleGrid[0].empty() || 1 == obstacleGrid[0][0])
return 0;
vector<vector<long>> dp(2);
for (auto i = 0; i < dp.size(); ++i)
dp[i].resize(obstacleGrid[0].size(), 0);
dp[0][0] = 1;
for (auto j = 1; j < dp[0].size(); ++j)
dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0;
auto cur = 1, prev = 0;
for (auto i = 1; i < obstacleGrid.size(); ++i) {
dp[cur][0] = obstacleGrid[i][0] == 0 ? dp[prev][0] : 0;
for (auto j = 1; j < dp[cur].size(); ++j)
dp[cur][j] = obstacleGrid[i][j] == 0 ? dp[prev][j] + dp[cur][j - 1] : 0;
prev = cur;
cur = 1 - cur; // 行索引只有0、1，和为1，可以靠减法求出下一次的值
}
return dp[prev].back();
}
};
PS2：可以利用62题的优化思路，进一步将空间复杂度降低到。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty() || obstacleGrid[0].empty() || 1 == obstacleGrid[0][0])
return 0;
vector<long> dp(obstacleGrid[0].size(), 1);
for (auto j = 1; j < dp.size(); ++j)
dp[j] = obstacleGrid[0][j] == 0 ? dp[j - 1] : 0;
for (auto i = 1; i < obstacleGrid.size(); ++i) {
dp[0] = obstacleGrid[i][0] == 0 ? dp[0] : 0;
for (auto j = 1; j < dp.size(); ++j)
dp[j] = obstacleGrid[i][j] == 0 ? dp[j] + dp[j - 1] : 0;
}
return dp.back();
}
};
