Share my ugly Java Solution. Easy to understand


  • 0
    S
      public static int minimumTotal(List<List<Integer>> triangle) {
        int length = triangle.size();
        List<List<Integer>> result = new LinkedList<>();
        List<Integer> first = new LinkedList<>();
        first.add(triangle.get(0).get(0));
        result.add(first);
    
        for(int i = 1 ; i<length; i++){ // start with triangle's second list. 
            List<Integer> list = new LinkedList<>();
            for(int j = 0; j<= i ; j++){
                if(j == 0)     list.add( triangle.get(i).get(0)+result.get(i-1).get(0));
                else if(j == i)   list.add(triangle.get(i).get(i)+result.get(i-1).get(i-1));
                else{
                    list.add(Math.min(triangle.get(i).get(j)+result.get(i-1).get(j-1),triangle.get(i).get(j)+result.get(i-1).get(j)) );
                }
            }
            result.add(list);
        }
    
        Integer min = Collections.min(result.get(length-1));
        return min;
    }
    

    The idea is to track every min total-value for every element of the lists.


Log in to reply
 

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