Unique Paths II

注意一个容易犯的错误：判断obstacleGrid是否为1时，else那部分不能少。因为如果不加，就会默认把那些值设置为0。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int height = obstacleGrid.size();int width = obstacleGrid[0].size();vector<vector<int>> result(height,vector<int>(width));if(obstacleGrid[0][0] == 1 || obstacleGrid[height-1][width-1] == 1)return 0;for(int i = 0;i < height;i++){for(int j = 0;j < width;j++){if(obstacleGrid[i][j] == 1)result[i][j] = 0;elseresult[i][j] = -1;}}result[0][0] = 1;for(int i = 0;i < height;i++){for(int j = 0;j < width;j++){if(i == 0 && j == 0)continue;if(result[i][j] == 0)continue;if(i != 0 && j != 0)result[i][j] = result[i][j-1] + result[i-1][j];else if(i == 0)result[i][j] = result[i][j-1];elseresult[i][j] = result[i-1][j];}}return result[height-1][width-1];}
};

初始化第一行第一列

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int length = obstacleGrid.size();if(length <= 0)return 0;int width = obstacleGrid[0].size();vector<vector<int>> result(length,vector<int>(width));if(obstacleGrid[0][0] == 1)result[0][0] = 0;elseresult[0][0] = 1;for(int i = 1;i < length;i++){if(obstacleGrid[i][0] == 1 || result[i-1][0] == 0)result[i][0] = 0;elseresult[i][0] = 1;}for(int j = 1;j < width;j++){if(obstacleGrid[0][j] == 1 || result[0][j-1] == 0)result[0][j] = 0;elseresult[0][j] = 1;}for(int i = 1;i < length;i++){for(int j = 1;j < width;j++){if(obstacleGrid[i][j] == 1)result[i][j] = 0;//else if(result[i-1][j] == 0)      这些不注释掉也能跑出正确结果//result[i][j] = result[i][j-1];//else if(result[i][j-1] == 0)//result[i][j] = result[i-1][j];elseresult[i][j] = result[i][j-1] + result[i-1][j];}}return result[length-1][width-1];}
};