minimum path sum of a number triangle

This is from leetcode: http://www.programcreek.com/2013/01/leetcode-triangle-java/

[
     [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). 

The key observation here is that viewing this triangle as a tree, for any given subtree, the minimum path sum is the minimum of all of its subtrees plus the number at the root. At the leaf level, the minimum path sum is the value at the leaves.

If we use dynamic programming, keep track of the minimum path sum at lower level, and then going up to calculate the min path sum at higher level.

	public static int minPath(List<int[]> input){
	int levels = input.size();
	int[][] dp = new int[levels][levels];
	//we start at the bottom
	//here the min path sum is the numbers at the bottom
	dp[levels-1] = input.get(levels-1);
	//now we go up
	for(int l=levels-2; l>=0; l--){
	for(int pos = 0; pos<=l; pos++){
	dp[l][pos] = Math.min(dp[l+1][pos], dp[l+1][pos+1]) + input.get(l)[pos];
	}
	}
	return dp[0][0];
	}

view raw gistfile1.java hosted with ❤ by GitHub

Further observation of the dynamic programming solution is that we don't need a 2D table, in stead we can use an array and keep on updating it when going up.

	public static int minPathBetter(List<int[]> input){
	int levels = input.size();
	int[] dp = new int[levels];
	//we start at the bottom
	//here the min path sum is the numbers at the bottom
	dp = input.get(levels-1);
	//now we go up
	for(int l=levels-2; l>=0; l--){
	for(int pos = 0; pos<=l; pos++){
	dp[pos] = Math.min(dp[pos], dp[pos+1]) + input.get(l)[pos];
	}
	}
	return dp[0];
	}

view raw minpath.java hosted with ❤ by GitHub