63. Unique Paths II
题目:
解答:
仍然是动态规划,但是,如果有阻挡,那么当前位置不可达,标记path总数为0
代码:
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size(), col = obstacleGrid[0].size();
vector<vector<int>> table(row, vector<int>(col));
table[0][0] = !obstacleGrid[0][0];
for(int i = 1;i < row; ++i){
if(obstacleGrid[i][0] == 1)
table[i][0] = 0;
else
table[i][0] = table[i-1][0];
}
for(int i = 1;i < col; ++i){
if(obstacleGrid[0][i] == 1)
table[0][i] = 0;
else
table[0][i] = table[0][i-1];
}
for(int i = 1;i < row; ++i){
for(int j = 1;j < col; ++j){
if(obstacleGrid[i][j] == 1)
table[i][j] = 0;
else
table[i][j] = table[i-1][j] + table[i][j-1];
}
}
return table[row-1][col-1];
}
};
更新会同步在我的网站更新(https://zergzerg.cn/notes/webnotes/leetcode/index.html)