Unique Paths II
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as
1and0respectively in the grid.For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]The total number of unique paths is
2.Note:m and n will be at most 100.
在Unique Paths 的基础上增加了障碍物。问从起点到终点有多少种走法。
解题思路：
基于上一篇博客，即Unique Paths这道题里的最后一个方法，就是空间复杂度O(min(m,n))的那个解法，接下来的算法的原理就是基于那个的。
因为起点到右边的点路径是唯一的，到下边点路径是唯一的。
所以可以得到一条重要的规律：
起点到终点的路径数等于右边那个点到终点路径数与下边那个点到终点路径数的和。
大概过程是酱紫的：
代码如下：
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<int> dp(n+1,0); m--; int i = n-1; while(i >= 0 && obstacleGrid[m][i] != 1){ dp[i] = 1; --i; } while(m-- > 0){ //这种循环判断可以将只有一行的情况统一考虑进去 for(i = n-1; i >= 0; i--){ dp[i] = (obstacleGrid[m][i] == 1)? 0 : dp[i+1] + dp[i]; } } return dp[0]; } };
【LeetCode练习题】Unique Paths II,布布扣,bubuko.com
原文：http://www.cnblogs.com/4everlove/p/3659628.html