Java DP solution, easy to understand


  • 0
    X
    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int res = Integer.MAX_VALUE;
            if(triangle == null || triangle.size() == 0) return res;
            int len = triangle.size();
            int[][]dp  = new int[len ][len ];
            for(int i = 0; i <= len -1  ; i++){
                dp[len -1][i] = triangle.get(len -1).get(i);
            }
            
            for(int i = len - 2; i>= 0; i--){
                for(int j = 0; j <= i; j++){
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
                }
            }
            return dp[0][0];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.