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

Note: 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.

s思路： 1. 最小路徑和，從上往下，下面的數的坐標只能是上一個數的坐標或坐標加1。枚舉所有路徑，然后找出最小值？ 2. 枚舉代碼功能正確，但是TLE?那必須是大量重復計算所致。分析如下： 如上圖，2到5的路徑有多條，也就是說從5開始往下遍歷需要遍歷多次，這就重復計算了！完全可以從上往下計算到每個位置的最小和，然后不斷迭代進行，也就是在每個位置計算最小和保存起來。這就是DP的思路！ 3. 以后做recursive的題，先看看是否會有重復計算，如有，則用DP??！