My java solution sharing


  • 0
    M
    1. O(N) Bottom Up Approach

      public int minimumTotal(List<List<Integer>> triangle) {

       int[] sum = new int[triangle.get(triangle.size()-1).size()];
       
       // initialize
       for(int i=0;i<triangle.get(triangle.size()-1).size();i++)
           sum[i] = triangle.get(triangle.size()-1).get(i);
       
       // calculate mininum    
       for(int i=triangle.size()-2;i>=0;i--){
           for(int j=0;j<triangle.get(i).size();j++){
               sum[j] = triangle.get(i).get(j) + Math.min(sum[j], sum[j+1]);
           }
       }
       return sum[0];
      

      }

    1. O(N) Top down Approach ( low performance )

    public int minimumTotal(List<List<Integer>> triangle) {
    List<Integer> subsum;
    List<Integer> curr;

        List<Integer> prev   = new ArrayList<>();
        prev.add(triangle.get(0).get(0));
        
        for(int i=1;i<triangle.size();i++){
            subsum = new ArrayList<>();
            curr   = triangle.get(i);
            
            // calculate the first element
            subsum.add(curr.get(0) + prev.get(0));
            
            
            // calculate elements in the middle
            for(int j=1;j<curr.size()-1;j++){
                subsum.add(Math.min(prev.get(j-1), prev.get(j)) + curr.get(j)); 
            }
            
            // calculate the last element
            subsum.add(prev.get(prev.size()-1) + curr.get(curr.size()-1));
            prev = subsum;
        }
        int min = Integer.MAX_VALUE;
        for(int i=0;i<prev.size();i++){
            min = Math.min(min, prev.get(i));
        }
        
        return min;
    }

Log in to reply
 

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