題目：
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
<code> [ [2], [3,4], [6,5,7], [4,1,8,3] ]/<code>
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.
題目大概意思就是從上往下經過最小的數字總和是多少，每一步只能移動到下面行的相鄰的數。
這個題其實也很簡單，利用遞歸將所有可能性都列舉出來，然後求出最小值，給出代碼：
<code> public static int minimumTotal(List<list>> triangle) { return getMinNext(triangle, 0, 0); } /** * * @param triangle * @param i 橫座標 * @param j 縱座標 * @return */ private static int getMinNext(List<list>> triangle, int i, int j) { if(j >= triangle.size()){ return 0; } if(i >= triangle.get(j).size()){ return 0; } int num = triangle.get(j).get(i); return Math.min(getMinNext(triangle, i, j + 1) + num, getMinNext(triangle, i + 1, j + 1) + num); }/<list>/<list>/<code>但是這樣的話，性能不好，其中
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
其中到第二行3的總長度=min(第三行6的總長度+第三行5的總長度)+3;
其中第三行6的總長度=min(第四行4的總長度+第四行1的總長度)+6;
第三行5的總長度又=min(第四行4的總長度+第四行8的總長度)+5;
這是第四行4的總長度 會被計算多次，導致最後性能不佳，可以利用一個數組來保存過去的值，
一開始將數組的值都設置成為-1，如果為-1我們就計算一下對應的值，如果不為-1就直接取出數組中的值，這樣實現代碼不是特別優雅。
這裡為了代碼整潔和優雅，我們採用動態規劃的思想來實現。
我們來看：
[
[2], 第三次循環 [11]
[3,4], 第二次循環 [9, 10]
[6,5,7], 第一次循環 [7, 6 10]
[4,1,8,3]
]
只需要這樣既可求出正確答案，貼出代碼：
<code>for (int j = triangle.size() - 2; j >=0 ; j--) { for (int i = 0; i < triangle.get(j).size(); i++) { Integer num = Integer.min(triangle.get(j + 1).get(i), triangle.get(j + 1).get(i + 1)) + triangle.get(j).get(i); triangle.get(j).set(i, num); } } return triangle.get(0).get(0);/<code>
閱讀更多 v心之所向v 的文章
