CLEAN CODE | TRIANGLE | DYNAMIC PROGRAMMING | PROGRAMMING | RUBY

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

https://leetcode.com/problems/triangle/description/

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
      end
      i+= 1
    end
    
    #p arr
    
    (1..width-1).each do |i|
      arr[i][0] += arr[i-1][0]
      i += 1
    end 
    
    (1..width-1).each do |i|
      (1..width-1).each do |j|
        if arr[i][j] >= 100000000000
          
        else
          arr[i][j] += [arr[i-1][j-1], arr[i-1][j]].min
        end 
      end
    end
    
   
      #p arr

    return arr[-1].min
end

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
linkedin

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 :)