Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
class Solution {
int uniquePaths(int m, int n) {
if(m <=0 || n <= 0) return 0;
vector<vector<int>> memo(m, vector<int>(n, 0));
return UP(m-1, n-1, memo);
int UP(int m, int n, vector<vector<int>> &memo){
//move out of boundary, it's invalid, should not be counted as a path
if(m < 0 || n <0) return 0;
//Robot hits the boundary, we can guarantee to have one way to reach the destination
if(m==0 || n==0) return 1;
if(memo[m][n] > 0) return memo[m][n];
//We calculate the sum of how many panths from two paths
return memo[m][n] = UP(m-1, n, memo) + UP(m, n-1, memo);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment