Easy to Understand Java top down DP solution with O(N) space


  • 1
    A
    public int minimumTotal(List<List<Integer>> triangle) {        
        if(triangle==null || triangle.size()==0) return 0;
    
        //init dp value to max integer, only the first is 0
        int[] dp = new int[triangle.size()];
        for(int i=1; i<triangle.size();i++){
            dp[i] = Integer.MAX_VALUE;
        }        
        
        //the next level dp[i] is based on  pre-level dp[i] or dp[i-1]
        //if i==0,  dp[i] =  currentList.get(i) + dp[i];
        //if i>0 ,  dp[i] =  currentList.get(i) + minimun of(dp[i-1], dp[i])
        for(List<Integer> list: triangle){
            for(int i=list.size()-1; i>=0;i--){
                dp[i] = list.get(i) + (i>0?Math.min(dp[i],dp[i-1]):dp[i]);
            }
        }
        
        //the result should be the minimum in dp
        int result = dp[0];
        for(int i=1;i<dp.length;i++){
            if(dp[i]<result){
                result = dp[i];
            }
        }
        return result;
    }

Log in to reply
 

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