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)