Min Sum Path in a Triangle - Algorithms and Problem SolvingAlgorithms and Problem Solving

Min Sum Path in a Triangle - Algorithms and Problem SolvingAlgorithms and Problem Solving

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  

Read full article from Min Sum Path in a Triangle - Algorithms and Problem SolvingAlgorithms and Problem Solving