Triangle

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

我们用动态规划来解决，从下往上开始相加，例如题目中的例子，最后一行是[4,1,8,3]，我们每次从中选取相邻两个元素中较小的那个与它上面序列[6,5,7]对应的元素相加, 4和1我们选取1，然后与6相加，1和8我们选取1与5相加，这样一直更新到最上面的一行，就是我们要找的结果。代码如下：

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null) return 0;
        for(int i = triangle.size() - 1; i > 0; i--) {
            for(int j = 0; j < triangle.get(i - 1).size(); j++) {
                triangle.get(i - 1).set(j, Math.min(triangle.get(i).get(j), triangle.get(i).get(j + 1)) + triangle.get(i - 1).get(j));
            }
        }
        return triangle.get(0).get(0);
    }
}

上面的代码没有什么问题，可以顺利AC，空间复杂度为O(1)。但是它改变了原有的数据，如果题目要求我们不能改变原有的数据，我们可以借助一个数组来完成。代码如下：

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null) return 0;
        int[] dp = new int[triangle.size() + 1];
        for(int i = triangle.size() - 1; i >= 0; i--) {
            for(int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}