Min Sum Path in a 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).

But for the following triangle –

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

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

The problem somewhat resemble a tree structure and hence finding minimum sum path from root to a leaf. But if we look carefully then we will notice that this is a simple dynamic programming problem as the problem is well defined. At each level we need to choose the node that yields a min total sum with the following relation –

dp[level][i] = triangle[level][i] + min{dp[next_level][i], dp[next_level][i+1]}

Notice that if we start from top and do a topdown dp then we might get wrong result as in example 2 it will return 15 = [2, 4, 5, 4]. But the actual minimum path is 13 = [2, 5, 5, 1]. That is we need to do a bottom-up computation for the dp. That is,

dp[level][i] = triangle[level][i] + min{dp[level+1][i], dp[level+1][i+1]}

Below is the implementation of this approach that runs in O(n^2) time and takes O(n^2) space.

//O(n^2) time and O(n^2) space for dp table
public static int triangleMinSumPath(List<int[]> triangle){
	int levels = triangle.size();
	int dp[][] = new int[levels][levels];
	
	dp[levels-1] = triangle.get(levels-1);
	
	//bottom up Dijkstra
	for(int l = levels-2; l>=0 ; l--){
		for(int i = 0; i<=l; i++){
			dp[l][i] = Math.min(dp[l+1][i], dp[l+1][i+1]) + triangle.get(l)[i];
		}
	}
	return dp[0][0];
}

O(n) space solution
If we print the dp table of the above code for example 2 then we will see the following –

Triangle - 

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


dp table  -

13,  0,  0, 0 
11, 13,  0, 0 
 6,  9, 10, 0 
 1,  4,  8, 3 

If we look closely then we can see that the table has meaningful values in lower half only and at each level bottom up we have one of the column value getting fixed. So, we could have basically used the bottom level array as the dp table and at each level we update the columns bottom up. In this way we can decrease the space from O(n^2) to O(n). Below is the modified implementation of the above code by using O(n) space for dp table.

//O(n^2) time and O(n) space 
public static int triangleMinSumPath2(List<int[]> triangle){
	int levels = triangle.size();
	int dp[] = new int[levels];
	
	dp = triangle.get(levels-1);
	
	//bottom up Dijkstra
	for(int l = levels-2; l>=0 ; l--){
		for(int i = 0; i<=l; i++){
			dp[i] = Math.min(dp[i], dp[i+1]) + triangle.get(l)[i];
		}
	}
	return dp[0];
}