120. Triangle

很简单的题目，一看就是DP。

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 0)
            return 0;
        if (triangle.size() == 1)
            return triangle.get(0).get(0);

        int size = triangle.size();
        // dp[i][j]表示达到第i行第j个节点所需要的最小路径
        int[][] dp = new int[size][size];
        // 初始状态
        dp[0][0] = triangle.get(0).get(0);

        int min = Integer.MAX_VALUE;
        for (int i = 1; i < size; i++) {
            for (int j = 0; j <= i; j++) {
                int thisValue = triangle.get(i).get(j);
                // 注意边界条件，两边的元素要特殊处理下
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + thisValue;
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + thisValue;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + thisValue;
                }

                // 如果是最后一行了
                if (i == size - 1) {
                    min = Math.min(min, dp[i][j]);
                }
            }
        }

        return min;
    }
}