原题
一个机器人位于一个 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. 向下 -> 向下 -> 向右 -> 向右
解法
思想
和leetcode62-不同路径类似，可以使用递归+记忆，每个位置的路径数为右边位置的路径数和下面位置的路径数之和，有障碍的点的路径数为0。
代码
class Solution {
int[][] grid;
Integer[][] paths;
int length;
int height;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
grid = obstacleGrid;
if(grid.length==0||grid[0].length==0) return 0;
height = grid.length;
length = grid[0].length;
paths = new Integer[height][length];
return getPaths(0,0);
}
public int getPaths(int m,int n){
if(m==height||n==length) return 0;
if(grid[m][n]==1) return 0;
if(m == height-1 && n==length-1) return 1;
if(paths[m][n] != null) return paths[m][n];
int ans = getPaths(m+1,n)+getPaths(m,n+1);
paths[m][n] = ans;
return ans;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode63-%e4%b8%8d%e5%90%8c%e8%b7%af%e5%be%84ii/
