By: Saurav

2018-03-19 05:51:00 UTC

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
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

These are medium level problems from Dynamic programming and essential to understanding DP. This has also been asked in an interview directly so its good to have a good understanding of how it works.

Just like in any DP the steps are:
Find the subproblem and visualize the recursive relation
Ths subproblem is to find the sum at a level if an element is taken into consideration.

Guess the solution for that subproblem
Here for any sum at a given place in the triangle, the sum can come from the element on the top or the element diagonally on the top

memoize the subproblems and recurse for the new one
For this, we take a two-dimensional square array of width equal to max width of the triangle array's subarray.
We start by guessing the sum value for the start elements in the first row and first column
Then we build the next solution by taking the minimum of two elements on top of the element (same column and last column) and then adding the element value to the sum.

Finally at the bottom array. we will have our solution.

Lets see the code:

(To have a clearer visualization, uncomment the p arr lines to see state of the array through the program)

def minimum_total(triangle)
    return 0 if triangle.length == 0 
    width = triangle[-1].length 
    arr = triangle.dup
    i = 0
    while i < width 
      while triangle[i].length < width
       arr[i] << 100000000000
      i+= 1
    #p arr
    (1..width-1).each do |i|
      arr[i][0] += arr[i-1][0]
      i += 1
    (1..width-1).each do |i|
      (1..width-1).each do |j|
        if arr[i][j] >= 100000000000
          arr[i][j] += [arr[i-1][j-1], arr[i-1][j]].min
      #p arr

    return arr[-1].min

Test Cases:

minimum_total([[-11]]) == -11
minimum_total([[-1],[2,3],[1,-1,-3]]) == -1
minimum_total([[2],[3,4],[6,5,7],[4,1,8,3]]) == 11

Let me know what you think!
twitter: sprakash24oct

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)