Leetcode -- Unique Paths II

Took some tuning work to get this right, essentially, dp + recursion

 class Solution {  
 public:  
   int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {  
     int m = obstacleGrid.size();  
     int n = obstacleGrid[0].size();  
     vector<vector<int> > cache(m, vector<int>(n, -1));  
     bool isObstacle = false;  
     for(int i = 0; i < m ; ++i) {  
       if(obstacleGrid[i][0]) {  
         isObstacle = true;  
       }  
       cache[i][0] = !isObstacle;  
     }  
     isObstacle = false;  
     for(int i = 0; i < n ; ++i) {  
       if(obstacleGrid[0][i]) {  
         isObstacle = true;  
       }  
       cache[0][i] = !isObstacle;  
     }  
     cache[0][0] = !obstacleGrid[0][0];  
     uniquePathsWithObstaclesHelper(m - 1, n - 1, obstacleGrid, cache);  
     return cache[m - 1][n - 1];  
   }  
   int uniquePathsWithObstaclesHelper(int m, int n, vector<vector<int> >& obstacleGrid, vector<vector<int> >& cache) {  
     if(m < 0 || n < 0) {  
       return 0;  
     }  
     if(m == 0 || n == 0) {  
       return cache[m][n];  
     }  
     if(obstacleGrid[m][n]) {  
       cache[m][n] = 0;  
       return 0;  
     }  
     int left = cache[m][n - 1] == -1 ? uniquePathsWithObstaclesHelper(m, n - 1, obstacleGrid, cache) : cache[m][n - 1];  
     int up = cache[m - 1][n] ? uniquePathsWithObstaclesHelper(m - 1, n, obstacleGrid, cache) : cache[m - 1][n];  
     cache[m][n] = left + up;  
     return cache[m][n];  
   }  
 };  

Better Approach

 class Solution {  
 public:  
   int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {  
     int m = obstacleGrid.size();  
     int n = obstacleGrid[0].size();  
     int dp[1000] = {-1};  
     dp[0] = !obstacleGrid[0][0];  
     for(int i = 0; i < m; ++i) {  
       for(int j = 0; j < n; ++j) {  
         if(j == 0) {  
           dp[j] = obstacleGrid[i][j] ? 0 : dp[j];  
           continue;  
         }  
         dp[j] = obstacleGrid[i][j] ? 0 : dp[j] + dp[j - 1];  
       }  
     }  
     return dp[n - 1];  
   }  
 };