UniquePathI_Memorization.cpp

class Solution {
public:
    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);
    }
};