Skip to content

Instantly share code, notes, and snippets.

@zhangxiaomu01
Created December 24, 2018 03:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zhangxiaomu01/d48cd7aec050e3bd340594f0ae2169c0 to your computer and use it in GitHub Desktop.
Save zhangxiaomu01/d48cd7aec050e3bd340594f0ae2169c0 to your computer and use it in GitHub Desktop.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& a) {
int row = a.size(), col = a[0].size();
if(a[0][0] == 1) return 0;
vector<vector<int>> memo(row, vector<int>(col));
return UPO(a, memo, row-1, col-1);
}
int UPO(vector<vector<int>> &a, vector<vector<int>> &b, int row, int col){
if(row <0 || col < 0) return 0;
else if(row == 0 && col == 0) return 1;
else if(b[row][col] > 0) return b[row][col];
else{
if(a[row][col] == 1) return 0;
b[row][col] = UPO(a, b, row-1, col) + UPO(a, b, row, col - 1);
return b[row][col];
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment