Q-12 Triangle - LeetCode 120

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        // return solve(triangle , 0 , 0 , new Integer[m][m]);

        //tabulization m*m | sc - m*m 
        /* tabulization always in bottom up fashion of recursion solution , so we will
        start from Mth row and our answer will be at 0,0 .
        */
        int[][] dp = new int[m][m];

        //base case
        for(int j = 0 ;j < m ; j++)
        dp[m-1][j] = triangle.get(m-1).get(j);

        //recursion logic bottom up going from m to 0
        for(int i= m-2 ; i >= 0 ;i-- ){
            for(int j = i ;j>=0 ;j--){
                int val = triangle.get(i).get(j);
                
                int down = dp[i+1][j];

                //handling for j = i
                int diag = dp[i+1][j+1];
                
                dp[i][j] = Math.min(down,diag ) + val ;
            }
        }
        return dp[0][0];
       
    }

    //recursion -> 2^(m*m) memoization-> 2*(m^m) | SC - m*m(stack height) + m*m (dp array)
    /* as the starting&ending point here is not fixed , we will write recursion in 0 to 
    last fashion , we are making calls from 0,0 and asking its neighours to return their
    minimum answers */
    public int solve(List<List<Integer>> triangle , int idx , int row , Integer[][] dp){
        int m = triangle.size();
        
        int val = triangle.get(row).get(idx);
        if(row == m-1)
        return val;

        if(dp[row][idx] != null)
        return dp[row][idx];

        //making left&right neighours calls from 0,0 to give their answers (faith)
        int down = solve(triangle , idx , row+1 , dp);
        int diag = solve(triangle , idx+1 , row+1 , dp);

        //adding our answer in minimum of them (expectation)
        //final answer will be returned from the root of the tree that is 0,0.
        return dp[row][idx] = Math.min(down , diag) + val;
    }
}