Triangle

Description

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).

Hint

Train of Thought

I have the same idea just as yours ,but that is java-version,transform"top to buttom"to "buttom to top"

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

is much more clear to understand

Code

public int minimumTotal1(List<List<Integer>> triangle) {
    int rowNum = triangle.size();
    int[] dp = new int[rowNum];
    for (int i = 0; i < triangle.get(rowNum - 1).size(); i++) {
        dp[i] = triangle.get(rowNum - 1).get(i);
    }
    for (int row = rowNum - 2; row >= 0; row--) {// for each layer
        for (int col = 0; col <= row; col++) {
            dp[col] = Math.min(dp[col], dp[col + 1])
                    + triangle.get(row).get(col);
        }
    }
    return dp[0];
}

public int minimumTotal(List<List<Integer>> triangle) {
    int rowNum = triangle.get(triangle.size() - 1).size();
    int colNum = triangle.size();
    int[][] dp = new int[rowNum][colNum];
    int i = 0;
    for (Integer n : triangle.get(colNum - 1)) {
        dp[rowNum - 1][i++] = n;
    }
    for (int row = rowNum - 2, m = 0; row >= 0; row--, m++) {
        for (int col = 0; col <= colNum - 2 - m; col++) {
            dp[row][col] = Math.min(dp[row + 1][col], dp[row + 1][col + 1])
                    + triangle.get(row).get(col);
        }
    }
    return dp[0][0];
}

Complexity