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

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