Leetcode Problem : 62 - Unique paths

Recursive Solution

class Solution {
    public int uniquePaths(int m, int n) {
        return countPath(m-1,n-1);
    }

    private int countPath(int i,int j){
        if(i == 0 && j == 0)return 1;
        if(i < 0 || j < 0)return 0;
        int up = countPath(i-1,j);
        int left = countPath(i,j-1);
        return up+left;
    }
}

Memoization

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] mem = new int[m][n];
        for(int [] col : mem){
            Arrays.fill(col,-1);
        }
        return countPath(m-1,n-1,mem);
    }

    private int countPath(int i,int j,int[][] mem){
        if(i == 0 && j == 0)return 1;
        if(i < 0 || j < 0)return 0;
        if(mem[i][j] !=-1)return mem[i][j];
        int up = countPath(i-1,j,mem);
        int left = countPath(i,j-1,mem);
        return mem[i][j]= up+left;
    }
}

Tabulation

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i == 0 && j==0)dp[i][j] = 1;
                else {
                    int up = 0;
                    int left = 0;
                    if(i > 0)up = dp[i-1][j];
                    if(j > 0)left = dp[i][j-1];
                    dp[i][j] = up+left;
                }
            }
        }

        return dp[m-1][n-1];

    }