小雨免费主机/宁波seo快速优化课程

### 解题思路

滚动数组优化动态规划

怎么判断是动态规划？

分析题目，挖掘 无后效性 和 最优子问题（最优子结构）

无后效性：当前问题的解只和前面问题的解有关，和后面问题的解无关。

最优子问题：当前问题的最优解取决于子问题的最优解，二者存在递推关系。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid.size() == 0 || obstacleGrid[0].size()==0) return 0;int m = obstacleGrid.size();int n= obstacleGrid[0].size();vector<int> dp(n, 0);if(obstacleGrid[0][0] == 0) dp[0] = 1;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(obstacleGrid[i][j]==1){dp[j]=0;continue;}if(j>=1) dp[j] = dp[j] + dp[j-1];//cur = up +  left}}return dp[n-1];}
};