(原地+dp) $O(n^2)$

Java 代码

/*
这里的注释的解法是：O(n^2) 一维dp(类似于背包问题的优化)
为什么只有在递减地枚举 j 时，才能省去一个一维数组？当我们在计算位置 (i,j) 时，
f[j+1] 到 f[i] 已经是第 i 行的值，而 f[0] 到 f[j] 仍然是第 i−1 行的值。此时我们直接通过递减来计算

相反，递增的枚举j时，会把i-1行的改变，变成了i行的值，而不是计算所需要的 原来 i-1行的值

*/
class Solution {
    public int minimumTotal(List<List<Integer>> f) {
        int n = f.size();
        // 自底向上求
        for(int i = n - 2; i >= 0; i --) {
            for(int j = 0; j <= i; j ++) {
                int t = Math.min(f.get(i + 1).get(j), f.get(i + 1).get(j + 1)) + f.get(i).get(j);
                f.get(i).set(j, t);
            }
        }
        return f.get(0).get(0);
    }
}