Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[     [2],    [3,4],   [6,5,7],  [4,1,8,3]]

 

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

public class Solution {    /**Top-down method. Since only O(n) extra memory is allowed, we use a deque to save the intermediate result.     * @author Averill Zheng     * @version 2014-06-23     * @since JDK 1.7     */    public int minimumTotal(List
     
      
       > triangle) {        int min = Integer.MAX_VALUE;		int length = triangle.size();		if(length == 0)			return 0;		else if(length == 1)			return triangle.get(0).get(0);		else {			Queue
       
         sums = new LinkedList
        
         ();			sums.add(triangle.get(0).get(0));			for(int i = 1; i < length; ++i){				List
         
           aList = triangle.get(i);				int equalIndex = sums.poll();				sums.add(equalIndex + aList.get(i));				int smallerIndex = (i > 1) ? sums.peek(): Math.abs(equalIndex); 				for(int j = i - 1; j > 0; --j){					sums.add(Math.min(smallerIndex + aList.get(j), equalIndex + aList.get(j)));									equalIndex = sums.poll();					smallerIndex = sums.peek(); 									}				sums.add(equalIndex + aList.get(0));			}			while(sums.peek() != null){				min = Math.min(min, sums.poll());			}		}		return min;    }}
         
        
       
      
     

 

method 2: bottom-up method

public class Solution {    public int minimumTotal(List
     
      
       > triangle) {        Queue
       
         sums = new LinkedList
        
         ();		int length = triangle.size();		if(length == 0)			return 0;		else if(length == 1)			return triangle.get(0).get(0);		else {			List
         
           lastList = triangle.get(length - 1);			for(int i = 0; i < length; ++i)				sums.add(lastList.get(i));			for(int i = length - 2; i > -1; --i){				List
          
            currentList = triangle.get(i); for(int j = 0; j < i + 1; ++j){ int equalIndex = sums.poll(); int largerIndex = sums.peek(); sums.add(currentList.get(j) + Math.min(equalIndex, largerIndex)); } sums.poll(); } } return sums.peek(); }}
          
         
        
       
      
     

 

method 3. bottom-up , and use List<Integer> as the data structure to save the intermediate result.

public class Solution {    public int minimumTotal(List
     
      
       > triangle) {        int length = triangle.size();		List
       
         pathSum = new ArrayList
        
         ();		if(length == 0)			return 0;				pathSum.addAll(triangle.get(length - 1));		for(int i = length - 2; i > -1; --i){			List
         
           aList = triangle.get(i);			for(int j = 0; j < i + 1; ++j)				pathSum.set(j, Math.min(pathSum.get(j), pathSum.get(j + 1))+ aList.get(j));		}		return pathSum.get(0);    }}