62. Unique Path

How many possible unique paths are there?

dynamic programming, space for time

iterative:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        
        // initialize edge case
        for (int i = 0; i<m; i++){
            memo[i][0]=1;
        }
        for(int j=0; j<n; j++){
            memo[0][j]=1;
        }
        for (int i = 1; i<m; i++){
            for(int j = 1; j<n; j++){
                // based ont on the results of sub-problems
                memo[i][j]=memo[i-1][j]+memo[i][j-1];
            }
        }
        return memo[m-1][n-1];
    }
    
}

recursive:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        return recursion(m-1, n-1, memo);       
    }
    
    private int recursion(int m, int n, int[][] memo){
        if (memo[m][n]!=0) return memo[m][n];
        if (m==0 || n == 0){
            return 1;
        }
        memo[m][n] = recursion(m-1, n, memo)+ recursion(m, n-1, memo);
        return memo[m][n];        
    }    
}