Triangle problem

Problem description:
Level: easy
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).

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.


Approach 1:
Dynamic programming: from bottom to top
Time: O(n^2)

add node value from the bottom to top level nodes
finally get a[0][0]

Approach 2:
Dynamic programming: from top to bottom
Time: O(n^2)
hint: add from a[0][0] to bottom
in level n: return the minimum value

Approach 3:
Binary tree DFS traverse
Time: O(2^n), not efficient when n > 10

Approach 4:
Binary tree DFS Divide & Conquer
Time: O(2^n), not efficient when n > 10

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">