108. Triangle

Work upward from the bottom row. Replace each cell with itself plus the smaller of the two cells directly beneath it. After collapsing every row, the apex holds the minimum top-to-bottom path sum.

Idea

Going top-down forces you to track many partial paths. Going bottom-up collapses them: the best path starting at a cell is that cell plus the cheaper of its two children below. Process rows from second-to-last up to the top, overwriting a rolling 1D array dp (initialized to the bottom row).

dp[j] = triangle[i][j] + min(dp[j], dp[j+1])

After the top row is processed, dp[0] is the answer.

Algorithm

1. dp = triangle[-1][:] (a copy of the bottom row).
2. For i from len(triangle) - 2 down to 0, for each j in row i: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).
3. Return dp[0].

Worked example: [[2],[3,4],[6,5,7],[4,1,8,3]]

• Start dp = [4,1,8,3].
• Row [6,5,7]: dp = [6+min(4,1), 5+min(1,8), 7+min(8,3)] = [7,6,10].
• Row [3,4]: dp = [3+min(7,6), 4+min(6,10)] = [9,10].
• Row [2]: dp = [2+min(9,10)] = [11].

Minimum total = 11 (path 2→3→5→1).

Complexity

• Time: O(n²) for a triangle with n rows.
• Space: O(n) — one rolling row.

class Solution {
    public int minimumTotal(int[][] triangle) {
        int n = triangle.length;
        int[] dp = new int[n];
        for (int j = 0; j < n; j++) {
            dp[j] = triangle[n - 1][j];
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}