题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
分析
题目说明每次 只能向下或者向右移动一步。那么我们分析每次走到a[m][n] 只能从上面那个格子a[m - 1][n] 或者从左边那个格子a[m][n - 1]过来，我们定义 a[m][n]是到当前格子的有多少种路径数。 所以我们的递推公式是： a[m][n] = a[m - 1][n] + a[m][n - 1];
- 注意： 第一行我们只能向右走， 第一列只能向下走。
- 如果上面或者左边格子是障碍物， 那么当前格子应该是 0， 但其实也符合
a[m][n] = a[m - 1][n] + a[m][n - 1]这个递推公式，这样我们判断格子是否是障碍物那么我们就设置为 0；
代码
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
let result = [];
let row = obstacleGrid.length;
let column = obstacleGrid[0].length
// 递推公式是 result[i][j] = result[i][j - 1] + result[i - 1][j]
for(let i = 0; i < row; i++) {
if(typeof result[i] == 'undefined') {
result[i] = [];
}
for(let j = 0; j < column; j++) {
let temp = obstacleGrid[i][j]
if(i === 0 && j === 0) {
result[i][j] = temp === 1 ? 0 : 1;
}
// 第一行只能向右走, 并且判断一下当前是不是障碍物，是的话那么走到当前路线的次数应该为0
if(i === 0 && j > 0) {
let tempLeft = obstacleGrid[i][j - 1];
result[i][j] = tempLeft || temp ? 0 : result[i][j - 1] ;
}
// 第一列只能向下走，并且判断一下当前是不是障碍物
if(j === 0 && i > 0) {
let tempUp = obstacleGrid[i - 1][j];
result[i][j] = (tempUp || temp ? 0 : result[i- 1][j]);
}
if(i > 0 && j > 0) {
const up = result[i - 1][j];
const left = result[i][j - 1];
result[i][j] = temp == 1 ? 0 : ( up + left);
}
}
}
return result[row - 1][column - 1]
};