Find the number of Unique Paths (Java)

Code

Spread the love

Tweet

A robot is located at the top-left corner of a m x n grid. It can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?

Java Solution 1 – DFS

A depth-first search solution is pretty straight-forward. However, the time of this solution is too expensive, and it didn’t pass the online judge.


public int uniquePaths(int m, int n) {
    return dfs(0,0,m,n);
}
 
public int dfs(int i, int j, int m, int n){
    if(i==m-1 && j==n-1){
        return 1;
    }
 
    if(i<m-1 && j<n-1){
        return dfs(i+1,j,m,n) + dfs(i,j+1,m,n);
    }
 
    if(i<m-1){
        return dfs(i+1,j,m,n);
    }
 
    if(j<n-1){
        return dfs(i,j+1,m,n);
    }
 
    return 0;
}

Java Solution 2 – Dynamic Programming


public int uniquePaths(int m, int n) {
    if(m==0 || n==0) return 0;
    if(m==1 || n==1) return 1;
 
    int[][] dp = new int[m][n];
 
    //left column
    for(int i=0; i<m; i++){
        dp[i][0] = 1;
    }
 
    //top row
    for(int j=0; j<n; j++){
        dp[0][j] = 1;
    }
 
    //fill up the dp table
    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
 
    return dp[m-1][n-1];
}

Java Solution 3 – Dynamic Programming with Memorization


public int uniquePaths(int m, int n) {
    int[][] mem = new int[m][n];
 
    //init with -1 value
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            mem[i][j]=-1;
        }
    }
 
    return helper(mem, m-1, n-1);
}
 
private int helper(int[][] mem, int m, int n){
    //edge has only one path
    if(m==0||n==0){
        mem[m][n]=1;
        return 1;
    }
 
    if(mem[m][n]!=-1){
        return mem[m][n];
    }
 
    mem[m][n] = helper(mem, m, n-1) + helper(mem, m-1, n);
 
    return mem[m][n];
}

Tags: Code, Java