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 end i+= 1 end #p arr (1..width-1).each do |i| arr[i] += arr[i-1] 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([,[3,4],[6,5,7],[4,1,8,3]]) == 11
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 :)