Number of Paths(Java Solution)

A Question on Pramp platform

There are three ways that you can solve it.

1. Memoization + recursive function

  static int[][] memo;
  static int numOfPathsToDest(int n) {
    // your code goes here
    memo = new int[n][n];
    for(int i = 0; i < n; i++){
      Arrays.fill(memo[i], -1);
    }
    return dp(n - 1, n - 1);
  }
  static int dp(int i, int j){
    if(i < j || i < 0 || j < 0) return 0;
    if(i == 0 && j == 0) return 1;
    if(memo[i][j] != -1) return memo[i][j];
    int record = dp(i - 1, j) + dp(i, j - 1);
    memo[i][j] = record;
    return record;
  }

2. bottom-up dynamic programming( SC: O(n²) )

The solution below uses bottom-up dynamic programming algorithm to solve it. The time complexity here is O(n²) and the space complexity here is O(n²).

static int numOfPathsToDest(int n) {
    // your code goes here
    if(n == 1) return 1;
    int[][] ans = new int[n][n];
    ans[0][0] = 1;
    for(int i = 0; i < n; i++){
      for(int j = i; j < n; j++){
        if(i > 0)
         ans[i][j] += ans[i-1][j];
        if(j > 0)
         ans[i][j] += ans[i][j - 1];              
      }
    }
    return ans[n-1][n-1];
}

3. bottom-up dynamic programming( SC: O(n) )

The solution below is a bit optimized it by minimizing the space complexity into O(n).

static int numOfPathsToDest(int n) {
    // your code goes here
    if(n == 1) return 1;
    int[] ans = new int[n];
    ans[0] = 1;
    for(int i = 0; i < n; i++){
      for(int j = 0; j <= i; j++){
        if(j > 0)
         ans[j] += ans[j - 1];              
      }
    }
    return ans[n-1];
}