首页 > 代码库 > leetcode--Triangle

leetcode--Triangle

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<List<Integer>> 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<Integer> sums = new LinkedList<Integer>();			sums.add(triangle.get(0).get(0));			for(int i = 1; i < length; ++i){				List<Integer> 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<List<Integer>> triangle) {        Queue<Integer> sums = new LinkedList<Integer>();		int length = triangle.size();		if(length == 0)			return 0;		else if(length == 1)			return triangle.get(0).get(0);		else {			List<Integer> 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<Integer> 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<List<Integer>> triangle) {        int length = triangle.size();		List<Integer> pathSum = new ArrayList<Integer>();		if(length == 0)			return 0;				pathSum.addAll(triangle.get(length - 1));		for(int i = length - 2; i > -1; --i){			List<Integer> 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);    }}