minimum path sum of a number triangle

This is from leetcode: http://www.programcreek.com/2013/01/leetcode-triangle-java/

[
     [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). 

The key observation here is that viewing this triangle as a tree, for any given subtree, the minimum path sum is the minimum of all of its subtrees plus the number at the root. At the leaf level, the minimum path sum is the value at the leaves.

If we use dynamic programming, keep track of the minimum path sum at lower level, and then going up to calculate the min path sum at higher level.




Further observation of the dynamic programming solution is that we don't need a 2D table, in stead we can use an array and keep on updating it when going up.