Open Tcdian opened 4 years ago
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
const dp = Array.from(
new Array(obstacleGrid.length),
() => new Array(obstacleGrid[0].length).fill(0)
);
for (let i = 0; i < obstacleGrid.length; i++) {
for (let j = 0; j < obstacleGrid[0].length; j++) {
if (obstacleGrid[i][j] === 0) {
if (i === 0 && j === 0) {
dp[i][j] = 1;
} else if(i === 0) {
dp[i][j] = dp[i][j - 1];
} else if (j === 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
}
}
return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
};
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
const dp: number[][] = Array.from(
new Array(obstacleGrid.length),
() => new Array(obstacleGrid[0].length).fill(0)
);
for (let i = 0; i < obstacleGrid.length; i++) {
for (let j = 0; j < obstacleGrid[0].length; j++) {
if (obstacleGrid[i][j] === 0) {
if (i === 0 && j === 0) {
dp[i][j] = 1;
} else if(i === 0) {
dp[i][j] = dp[i][j - 1];
} else if (j === 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
}
}
return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
};
63. Unique Paths II
一个机器人位于一个
m x n
网格的左上角 (起始点在下图中标记为“Start”
)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为
“Finish”
)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
Example 1
Note
1 <= m, n <= 100