DP #120 Triangle

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // int r=triangle.size();
        // int[][] dp=new int[r][r];
        // for(int[] i:dp)Arrays.fill(i,-1);
        // int ans=(int)Math.pow(10,9);
        // for(int i=0;i<r;i++){
        //     ans=Math.min(ans,func(r-1,i,triangle,dp));
        // }
        // return ans;
        // return tabOpt(triangle);
        return tab2(triangle);
    }

    // Tabulation Solution 2
    int tab2(List<List<Integer>> tr){
        int r = tr.size();
        int[][] dp = new int[r][r];
        for(int i=0;i<r;i++) dp[r-1][i] = tr.get(r-1).get(i);

        for(int i=r-2;i>=0;i--){
            for(int j=i;j>=0;j--){

                int down = tr.get(i).get(j) + dp[i+1][j];
                int dia = tr.get(i).get(j) + dp[i+1][j+1];
                dp[i][j]=Math.min(down,dia);
            }
        }
        return dp[0][0];
    }

    // Tabulation Space Optimised Solution
    int tabOpt(List<List<Integer>> tr){
        int r=tr.size();
        int[] dp = new int[r];
        int ans=(int)Math.pow(10,9);
        for(int i=0;i<r;i++){
            int[] cur = new int[r];
            for(int j=0;j<=i;j++){
                if(i==0&&j==0) {
                    cur[j]=tr.get(i).get(j);
                    if(i==r-1)ans=Math.min(ans,cur[j]);
                    continue;
                }
                int up=tr.get(i).get(j) + ((i-1>=j)?dp[j]:(int)Math.pow(10,9));
                int dia=tr.get(i).get(j) + ((j-1>=0)?dp[j-1]:(int)Math.pow(10,9));
                cur[j]=Math.min(up,dia);
                if(i==r-1)ans=Math.min(ans,cur[j]);
                // System.out.println(i+"::"+j+"::"+dp[i][j] + " ");
            }
            dp=cur;
        }

        return ans;
    }

    // Tabulation Solution
    int tab(List<List<Integer>> tr){
        int r=tr.size();
        int[][] dp = new int[r][r];
        int ans=(int)Math.pow(10,9);
        for(int i=0;i<r;i++){
            for(int j=0;j<=i;j++){
                if(i==0&&j==0) {
                    dp[i][j]=tr.get(i).get(j);
                    if(i==r-1)ans=Math.min(ans,dp[i][j]);
                    continue;
                }
                int up=tr.get(i).get(j) + ((i-1>=j)?dp[i-1][j]:(int)Math.pow(10,9));
                int dia=tr.get(i).get(j) + ((j-1>=0)?dp[i-1][j-1]:(int)Math.pow(10,9));
                dp[i][j]=Math.min(up,dia);
                if(i==r-1)ans=Math.min(ans,dp[i][j]);
                // System.out.println(i+"::"+j+"::"+dp[i][j] + " ");
            }
        }

        return ans;
    }

    // Recursion Memoization Solution
    int func(int r, int c, List<List<Integer>> tr,int[][] dp){
        if(r==0&&c==0) return tr.get(r).get(c);
        if(c>r) return (int)Math.pow(10,9);
        if(r<0 || c<0)return (int)Math.pow(10,9);
        if(dp[r][c]!=-1) return dp[r][c];
        int up = tr.get(r).get(c) + func(r-1,c,tr,dp);
        int dia = tr.get(r).get(c) + func(r-1,c-1,tr,dp);
        return dp[r][c]=Math.min(up,dia);
    }
}