思路：

用到dp的思想，到row,col点路径数量 ：

path[row][col]=path[row][col-1]+path[row-1][col];

遍历row*col，如果map[row][col]为1，则将其置为0；如果非1，则进行上述公式。

最后返回path[终点row][终点col]的值即为解。

一开始的代码，beat 44%，效率不高

class Solution { public:  int uniquePathsWithObstacles(vector
    
     
      > &obstacleGrid) {    int rowSize = obstacleGrid.size();    int colSize = obstacleGrid[0].size();    if (obstacleGrid[0][0] == 1) return 0;    obstacleGrid[0][0] = 1;    for (int col = 1; col < colSize; col++) {      if (obstacleGrid[0][col] == 1)        obstacleGrid[0][col] = 0;      else        obstacleGrid[0][col] += obstacleGrid[0][col - 1];    }    for (int row = 1; row < rowSize; row++) {      if (obstacleGrid[row][0] == 1)        obstacleGrid[row][0] = 0;      else        obstacleGrid[row][0] += obstacleGrid[row-1][0];    }    for (int i = 1; i < rowSize; i++) {      for (int j = 1; j < colSize; j++) {        if (obstacleGrid[i][j] == 1)          obstacleGrid[i][j] = 0;        else          obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];      }    }    return obstacleGrid[rowSize - 1][colSize - 1];  }};
     
    

优化后的代码：

使用额外一个数组记录走到每一列有几种走法，因为题目只求终点，则使用一维数组即可。

使用一个额外的整型pre记录当前的前一步有多少种走法。（左边走来+上边走来）

则有：

pre(当前)=dp[col](上一行当前列) + pre(左一格当前行);dp[col](当前)=pre;

beat 100%

class Solution { public:  int uniquePathsWithObstacles(vector
    
     
      > &obstacleGrid) {    int rowSize = obstacleGrid.size();    int colSize = obstacleGrid[0].size();    int dp[colSize] = {0};    int pre = 1;    for (int i = 0; i < rowSize; i++) {      for (int j = 0; j < colSize; j++) {        if (obstacleGrid[i][j] == 0) {          pre += dp[j];          dp[j] = pre;        }        else {          pre = 0;          dp[j] = 0;        }      }      pre=0;    }    return dp[colSize-1];  }};