http://www.lintcode.com/zh-cn/problem/unique-paths-ii/
在上一题的基础上加入了障碍物。
同样可采用递归实现，递推公式不变，但是需要加入对障碍物的判断。
下面是实现的代码：
1 #include2 #include 3 class Solution { 4 public: 5 /** 6 * @param obstacleGrid: A list of lists of integers 7 * @return: An integer 8 */ 9 int solute(vector > &v, vector > &f, int m, int n)10 {11 if(f[m][n]!=-1) return f[m][n];12 int M = v.size(), N = v[0].size();13 if(v[M-m][N-n]==1) f[m][n] = 0;14 else if(m==1&&n==1) f[m][n] = 1;15 else if(m==1) f[m][n] = min(1, solute(v, f, 1, n-1));16 else if(n==1) f[m][n] = min(1, solute(v, f, m-1, 1));17 else f[m][n] = solute(v, f, m-1, n)+solute(v, f, m, n-1);18 return f[m][n];19 }20 int uniquePathsWithObstacles(vector > &v) {21 // write your code here22 int m = v.size(), n = v[0].size();23 vector > f(m+1, vector (n+1, -1));24 return solute(v, f, m, n);25 }26 };
