LeetCode: triangle

April 4, 2014 - work on one leetcode algorithm - dynamic programming about the triangle.

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Read 3 websites:

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

Best solution:

http://fmarss.blogspot.ca/2014/10/triangle.html

Not optimal one:

http://yucoding.blogspot.ca/2013/04/leetcode-question-112-triangle.html

Cloud not figure out the best solution with the example, and then, read this website with an example:

http://www.mathblog.dk/project-euler-18/

I got it. Using dynamic programming, and also from bottom to up. Here is the summary of algorithm using the example:

We start with a triangle that looks like

3
7 4
2 4 6
8 5 9 3

Applying the algorithm to the small problem we will need three iterations. The first iteration we apply the rule a + max(b,c) which creates a new triangle which looks as

3
7 4
10 13 15

Making the second iteration of the algorithm makes the triangle look

3
20 19

And if we run the algorithm once more, the triangle collapses to one number – 23 – which is the answer to the question.