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; } }