原题地址：https://leetcode.cn/problems/unique-paths-ii/
题解
这道题和62. 不同路径 大同小异，唯一的不同就是增加了障碍物
设dp[r][c]为机器人达到坐标[r,c]可能的路径数，我们知道机器人只能通过[r-1,c]或者[r,c-1]来达到[r,c]，所以对于路径数我们有：
考虑几种特殊情况：
- 对于障碍物而言，遇到可以直接将dp[r][c]设置为0并continue
- 当机器人的初始坐标即为障碍物时，机器人无法移动，可以直接返回0
时间复杂度：O(N)
空间复杂度：O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid[0][0]==1)return 0;
int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];
dp[0][0]=1;
for(int r=0;r<dp.length;r++){
for(int c=0;c<dp[r].length;c++){
if(obstacleGrid[r][c]==1)continue;
dp[r][c]+=(r>0?dp[r-1][c]:0)+(c>0?dp[r][c-1]:0);
}
}
return dp[dp.length-1][dp[0].length-1];
}
}
|
