120. 三角形最小路径和

解法一：动态规划

dp[i][j] 表示到达 (i, j) 时的最小路径和，则有以下状态转移方程：

import java.util.Arrays;
import java.util.List;
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        final int depth = triangle.size();
        // dp[i][j]表示到达(i, j)时的最小路径和
        int[][] dp = new int[depth][depth];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < depth; ++i) {
            // 行首和行尾单独处理
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int ans = Integer.MAX_VALUE;
        for (int i : dp[depth - 1]) {
            ans = Math.min(ans, i);
        }
        return ans;
    }
}

解法二：动态规划

有了第一种做法，可以发现每次计算当前层时只用到了上一层的结果，因此在空间使用上可以进行压缩，改用一维数组来存储。要注意这时更新结果要倒序进行，否则部分上一层待使用的结果会被下一层的的新数据代替。当然也可以用两个数组分别存储上一层和当前层的结果，每计算完一层就更新，这样就可以不用考虑顺序的问题。

import java.util.Arrays;
import java.util.List;
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        final int depth = triangle.size();
        // dp[i]表示到达当前层第i格时的最小路径和
        int[] dp = new int[depth];
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < depth; ++i) {
            // 倒序更新每一格
            // 这样前面的格子更新时依然使用上一层的结果, 不会受到影响
            dp[i] = dp[i - 1] + triangle.get(i).get(i);
            for (int j = i - 1; j > 0; --j) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
            }
            dp[0] = dp[0] + triangle.get(i).get(0);
        }
        int ans = Integer.MAX_VALUE;
        for (int i : dp) {
            ans = Math.min(ans, i);
        }
        return ans;
    }
}