三角矩阵

思路：
动规题目，我们需要分析出状态，状态转移方程，初始状态和返回结果

• 方式① 自上向下解决

代码实现：

public int minTotal(ArrayList<ArrayList<Integer>> triangle){
    if(triangle.isEmpty()){
        return 0;
    }
    List<List<Integer>> min = new ArrayList<>();
    for(int i = 0; i < triangle.size(); ++i) {
        min.add(new ArrayList<>());
    }
    // F[0][0]初始化
    min.get(0).add(triangle.get(0).get(0));
    for(int i = 1; i < triangle.size(); ++i) {
        int curSum = 0;
        for(int j = 0; j <= i; ++j) {
            // 左边界
            if(j == 0) {
                curSum = min.get(i - 1).get(0);
            }
            // 右边界
            else if(j == i){
                curSum = min.get(i - 1).get(j - 1);
            }
            else{
                curSum = Math.min(min.get(i - 1).get(j),
                        min.get(i - 1).get(j - 1));
            }
            // F(i,k) = min( F(i-1, k-1), F(i-1, k)) + triangle[i][k]
            min.get(i).add(triangle.get(i).get(j) + curSum);
        }
    }
    int size = triangle.size();
    // min(F(n-1, i))
    int minResult = min.get(size - 1).get(0);
    for(int i = 1; i < size; ++i) {
        minResult = Math.min(minResult,min.get(size - 1).get(i));
    }
    return minResult;
}

方式① 的问题是，新增一个数组min[ ] 来保存当前层到下一层各个节点最短的路径值，但是由于获得下一层结点的最短路径时，当前数组的各个值会用到两次，那么就不可能在计算下一层的最短结点的时候逐个覆盖当前数组的值，因此需要再增加一个数组，来交替存储最新的最短路径值，但这样就不满足 O(N) 的空间复杂度

• 方式② 自下向上解决

代码实现：

public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
    if (triangle.isEmpty()){
        return 0;
    }
    //记录三角形的层数
    int row = triangle.size();
    //创建一个暂存数组，用于存放到达每一层各个节点的最小步数
    int[] temp = new int[row];
    //先初始化temp数组，暂存最后一层的结点
    for (int i = 0; i < row; i++)
        temp[i] = triangle.get(row-1).get(i);
    //然后向上运算，到达上一层的最小值，应该是当前层的结点，也就是暂存数组的元素两两比较的最小值和上一层结点的相加
    for(int i = row - 2; i >= 0; i--){
        for(int k = 0; k <= i; k++){
            temp[k] = triangle.get(i).get(k) + Math.min(temp[k],temp[k + 1]);
        }
    }
    return temp[0];
}

方式② 需要用到额外的一个数组，temp[n]，O(N) 的空间复杂度，当计算到达上一层的最短路径并覆盖存储到 temp[n] 数组时，覆盖的那个节点已经不需要再次使用了，所以不需要再新增一个数组