题目：
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
思路：
直接通过记忆化深搜解决
代码：
class Solution {
public:
int dfs(vector<vector<int>>& obstacleGrid, int curRow, int curCol, vector<vector<int>>& dp) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
if (curRow == m - 1 && curCol == n - 1) return 1;
if (dp[curRow][curCol] > -1) return dp[curRow][curCol];
int down = 0, right = 0;
if (curRow + 1 < m && obstacleGrid[curRow + 1][curCol] == 0) down = dfs(obstacleGrid, curRow + 1, curCol, dp);
if (curCol + 1 < n && obstacleGrid[curRow][curCol + 1] == 0) right = dfs(obstacleGrid, curRow, curCol + 1, dp);
dp[curRow][curCol] = down + right;
return down + right;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<vector<int>> dp(101, vector<int>(101, -1));
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1) return 0;
if (m == 1 && n == 1 && obstacleGrid[0][0] == 0) return 1;
else if (m == 1 && n == 1 && obstacleGrid[0][0] == 1) return 0;
return dfs(obstacleGrid, 0, 0, dp);
}
};