Leetcode 120. 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).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

题意：在一个二维数组表示的三角形中，找一个从定点到底的路径和最小的一条路径。

思路：
第一种方法是用深度优先搜索暴力的求解每个路径和，找到最短的路径和，因为每个点下面都有两条路可以走，所以时间复杂度是2的n次方级别。
第二种方法是用动态规划的思路。用dp[i][j]表示从顶点2到第i层j列位置的最短路径和，由图可知，从上层有两个位置能到达，如果知道了上层两个位置的dp[i-1][j-1]和dp[i-1][j]，则dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + array[i][j]。三角形的两条腰是特殊情况，它们只能从上层一个位置到达。

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }

    int len = triangle.size();
    int[][] dp = new int[len][len];
    dp[0][0] = triangle.get(0).get(0);
    int min = Integer.MAX_VALUE;
    for (int i = 1; i < len; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
            } else if (j == i) {
                dp[i][j] = dp[i - 1][i - 1] + triangle.get(i).get(j);
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            if (i == len - 1) {
                min = Math.min(min, dp[i][j]);
            }
        }
    }

    return min == Integer.MAX_VALUE ? dp[0][0] : min;
}

题目还要求能否用O(n)的空间复杂度解决，参看discuss的答案，他的思路和自己的思路是一样的，只不过是从底向顶点推到，即dp[i]代表从当前层第i列走到底的最短路径和，而我写的dp状态是从顶点到当前位置的最短路径和。

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