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[, [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).
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.
It is a good practice to approach this problem using dynamic programming technique. However, at first the array looks like a tree from its form, where quickly people think to traverse the numbers using DFS. If we look carefully, every node here always shares a child which is an “overlapping subproblems”. For example from the above example, in the 2nd row: 3 has 6 and 5 as children; 4 has 5 and 7 as children. Here, 5 is both child for 3 and 4. Going down to the bottom we will find more shared children. Clearly this is a dynamic programming problem.
This can be solved using both top-down or bottom-up techniques. I would pick bottom-up as this is pretty straight forward. We will go from the second last row. Path sum of a node will be the minimum value of its two children plus its own value. From the above example, in case of row 3 (2nd last row), path sum of 6 will be ‘min(4,1) + 6’. By generalizing this, we will get the bottom-up approach as below with space complexity O(1) and time complexity O(n^2):
def min_sum(triangle): if not triangle: return None for i in range(len(triangle)-2, -1, -1): for j in range(len(triangle)): triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]) return triangle
A slightly different bottom-up approach if we don’t want to change the original input due to thread safe issue or whatever reason. This is going to be O(n) space complexity. Note that when we compute a row, rows after this would be useless for the result, thus we can do this by using 1D array and iteratively update itself.
def min_sum(triangle): if not triangle: return None res = triangle[-1] for i in range(len(triangle)-2, -1, -1): for j in range(len(triangle)): res[j] = min(res[j], res[j+1]) + triangle[i][j] return res