Triangle(recursive && dp) soln

Roshan Jha

·

Follow

2 min read

·

Nov 26, 2023

--

Listen

Share

//using simple recursion
import java.util.* ;
import java.io.*; 
public class Solution {
    public static int minimumPathSum(int[][] triangle, int n) {
        // Write your code here.
        return f(0,0, triangle,n);
        
    }
    static int f(int i,int j,int[][] triangle, int n){
        if(i==n-1){
            return triangle[i][j];
        }
        int down=triangle[i][j]+f(i+1,j,triangle,n);
        int dg=triangle[i][j]+f(i+1,j+1,triangle,n);
        return Math.min(down, dg);
    }
}
//Time Complexity: Exponential, O(2^n), as there are repeated function calls.
//Space Complexity: O(n), where n is the depth of the recursion.

//using Memoization
import java.util.* ;
import java.io.*; 
public class Solution {
    public static int minimumPathSum(int[][] triangle, int n) {
        int [][] dp=new int[n][n];
      for(int i=0;i<n;i++){
          Arrays.fill(dp[i],-1);
      }
        // Write your code here.
        return f(0,0, triangle,n,dp);
        
    }
    static int f(int i,int j,int[][] triangle, int n,int[][]dp){
        if(i==n-1){
            return triangle[i][j];
        }
        if(dp[i][j]!=-1) return dp[i][j];
        int down=triangle[i][j]+f(i+1,j,triangle,n,dp);
        int dg=triangle[i][j]+f(i+1,j+1,triangle,n,dp);
        return dp[i][j]=Math.min(down, dg);
    }
}
//Time Complexity: O(n^2), as each subproblem is solved once.
//Space Complexity: O(n^2), due to the memoization table.

//tabulation
import java.util.* ;
import java.io.*; 
public class Solution {
    public static int minimumPathSum(int[][] triangle, int n) {
        int [][] dp=new int[n][n];
        //base case
        for(int i=0;i<n;i++){
            dp[n-1][i]=triangle[n-1][i];
        }
        for(int i=n-2;i>=0;i--){
            for(int j=i;j>=0;j--){
                int down=triangle[i][j]+dp[i+1][j];
                int dg=  triangle[i][j]+dp[i+1][j+1];
                dp[i][j]=Math.min(down, dg);
            }
        }
        return dp[0][0];
        
    }
   
}
//Time Complexity: O(n^2), as each entry is calculated once.
//Space Complexity: O(n^2), due to the tabulation table.

//space optimization
import java.util.* ;
import java.io.*; 
public class Solution {
    public static int minimumPathSum(int[][] triangle, int n) {
        int [] front=new int[n];
         int [] curr=new int[n];
        //base case
        for(int i=0;i<n;i++){
            front[i]=triangle[n-1][i];
        }
        for(int i=n-2;i>=0;i--){
     
            for(int j=i;j>=0;j--){
                int down=triangle[i][j]+front[j];
                int dg=  triangle[i][j]+front[j+1];
               curr[j]=Math.min(down, dg);
            }
            System.arraycopy(curr, 0, front, 0, n);
        }
        return front[0];
        
    }
   
}
//Time Complexity: O(n^2), as each entry is calculated once.
//Space Complexity: O(n), as only two arrays (front and curr) are used.