109. Triangle

Description

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

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.

Example

Example 1:

Input the following triangle:

[

    [2],

    [3,4],

  [6,5,7],

  [4,1,8,3]

]

Output: 11

Explanation: The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Example 2:

Input the following triangle:

[

    [2],

    [3,2],

  [6,5,7],

  [4,4,8,1]

]

Output: 12

Explanation: The minimum path sum from top to bottom is 12 (i.e., 2 + 2 + 7 + 1 = 12).

思路：

一共有四种

• DFS: Traverse，用全局变量， 时间复杂度O(n2)，在lintcode里会超时

• DFS: Divide Conquer, 选两边之和比较小的一边，复杂度O(2^n),依然会超时

• Divide Conquer + Memoization,时间复杂度会被降到n!

• Traditional Dynamic Programming 用传统动态规划的方程解决，记住动态规划的四要素。

代码：