Easy understand solution(seems to be DP)


  • 0

    Update the array accordingly and get the minimum value in the end. Hope it helps. Any comment is welcome.

    public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle == null) return 0;
            
            int len = triangle.size();
            int[] ret = new int[len];
            Arrays.fill(ret, 0);
            ret[0] = triangle.get(0).get(0);
            
            for(int i = 1; i < len; i ++){
                for(int j = i; j >= 0; j --){
                    if(j == i){ ret[j] = ret[i - 1] + triangle.get(i).get(j); }
                    if(j == 0){ ret[j] = ret[0] + triangle.get(i).get(0); }
                    if(j > 0 && j < i){
                        ret[j] = Math.min(ret[j], ret[j - 1]) + triangle.get(i).get(j);
                    }//if
                }//for(j)        
            }//for(i)
            
            int min = Integer.MAX_VALUE;
            for(int num : ret){ min = Math.min(min, num); }
            return min;
        }
    

Log in to reply
 

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