原题 思路： 用到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<vector<int>> &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<vector<int>> &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]; } };转载于:https://www.cnblogs.com/ruoh3kou/p/9893422.html
相关资源：数据结构—成绩单生成器