题目

分析
与62题不同的地方在于添加了障碍物,导致边界条件变得不一样了。
边界条件:第一行,从左往右数,如果哪个位置出现了障碍,那么之后的位置就都为0,因为机器人就再也不可达了。第一列同理。
状态转移方程不变。需要注意,如果当前位置为障碍,那么dp[i][j] = 0。
代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& nums) {
//初始位置就有障碍,则不可达
if (nums.empty() || nums[0][0] == 1){
return 0;
}
int row = nums.size();
int col = nums[0].size();
//终点有障碍,则不可达
if (nums[row - 1][col - 1] == 1){
return 0;
}
vector<vector<long long>> dp(row, vector<long long>(col, 0));
//初始化第一行
int k = 0, cur = 1;
while (k < col){
if (nums[0][k] == 1){
cur = 0;
}
dp[0][k++] = cur;
}
//初始化第一列
k = 0, cur = 1;
while (k < row){
if (nums[k][0] == 1){
cur = 0;
}
dp[k++][0] = cur;
}
//开始dp
for (int i = 1; i < row; i++){
for (int j = 1; j < col; j++){
if (nums[i][j] == 1){
continue;
}
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[row - 1][col - 1];
}
};
网友评论