Topics › Dynamic Programming › 2D/3D DP and DP on Grids

Triangle

Medium TUF ID 299 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a triangle of integers: row i has i + 1 numbers. Starting at the single number on top, move down one row at a time. From position j in row i you may move to position j or position j + 1 in row i + 1. Return the minimum sum of a path from the top to any number in the bottom row.

This is LeetCode 120: 1 ≤ n ≤ 200 rows, values in [-10^4, 10^4]. LeetCode passes the triangle as List<List<Integer>>; the Java methods take a jagged int[][] where triangle[i] has length i + 1, which reads the same way.

Example 1

    2
   3 4
  6 5 7
 4 1 8 3
answer = 11         // 2 + 3 + 5 + 1

Example 2

triangle = [[-10]]
answer = -10        // a single row: the path is just the apex

Fixed start, variable end

The path always starts at the apex (0, 0) but can end at any of the n cells of the last row. That suggests writing the recursion from the fixed end: let the state be “I am at (i, j) and still have to go down”. Then the base case is the last row, where the remaining path is just the current cell, and no loop over possible end cells is needed. (Minimum Falling Path Sum had both ends variable, which forced such a loop.)

The tabulation then runs in the opposite direction to the recursion: from the last row up to the apex, and the answer ends up in a single cell, dp[0][0].

Approach 1: Recursion

Intuition. Let f(i, j) be the minimum sum of a path from (i, j) down to the bottom row, including triangle[i][j] itself. From (i, j) the path continues either straight down to (i + 1, j) or diagonally to (i + 1, j + 1). Whichever it takes, the rest should be the cheapest path from there. So

f(n - 1, j) = triangle[n - 1][j]
f(i, j)     = triangle[i][j] + min( f(i + 1, j), f(i + 1, j + 1) )
answer      = f(0, 0)

Both moves always stay inside the triangle, because row i + 1 is one cell longer than row i, so no bounds checks are needed.

Algorithm.

1. If i is the last row, return triangle[i][j].
2. Otherwise return triangle[i][j] + min(f(i + 1, j), f(i + 1, j + 1)).

static int recursive(int[][] triangle) {
    return solve(0, 0, triangle);
}

static int solve(int i, int j, int[][] triangle) {
    if (i == triangle.length - 1) return triangle[i][j];    // last row: the path ends here
    int down = solve(i + 1, j, triangle);
    int diagonal = solve(i + 1, j + 1, triangle);
    return triangle[i][j] + Math.min(down, diagonal);
}

Complexity. Time O(2^n): each call branches twice for n - 1 levels, one branch per top-to-bottom path. Space O(n) for the recursion depth.

Greedy, always stepping to the smaller of the two children, is not enough. On the triangle [[1], [2, 9], [10, 1, 1], [10, 10, 10, 1]] greedy goes 1 -> 2 -> 1 -> 10 = 14, but 1 -> 9 -> 1 -> 1 = 12. The cheap first step leads to a region where every exit is expensive.

Approach 2: Memoization

Intuition. A cell (i, j) is reached from both (i - 1, j - 1) and (i - 1, j), so plain recursion re-solves it many times. There are only n(n + 1) / 2 cells; cache each answer.

Values can be negative, so -1 cannot mark “not computed”. The table, jagged like the triangle, is filled with Integer.MAX_VALUE, which no real path sum can equal.

Algorithm.

1. Create a jagged dp with row i of length i + 1, filled with Integer.MAX_VALUE.
2. In the helper, return the last-row value directly; otherwise return the cached value if present, or compute, store and return it.

static int memoization(int[][] triangle) {
    int n = triangle.length;
    int[][] dp = new int[n][];
    for (int i = 0; i < n; i++) {
        dp[i] = new int[i + 1];
        Arrays.fill(dp[i], Integer.MAX_VALUE);              // MAX_VALUE = not computed (sums can be negative)
    }
    return memo(0, 0, triangle, dp);
}

static int memo(int i, int j, int[][] triangle, int[][] dp) {
    if (i == triangle.length - 1) return triangle[i][j];
    if (dp[i][j] != Integer.MAX_VALUE) return dp[i][j];
    int down = memo(i + 1, j, triangle, dp);
    int diagonal = memo(i + 1, j + 1, triangle, dp);
    return dp[i][j] = triangle[i][j] + Math.min(down, diagonal);
}

Complexity. Time O(n^2): each of the n(n + 1) / 2 cells is computed once. Space O(n^2) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. f(i, j) depends on row i + 1, so fill the table bottom-up. The last row is the base case and is copied straight from the triangle. Each row above takes its own value plus the smaller of the two cells beneath it.

Algorithm.

1. dp[n - 1] = copy of triangle[n - 1].
2. For i from n - 2 down to 0, for j from 0 to i: dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1]).
3. Return dp[0][0].

static int tabulation(int[][] triangle) {
    int n = triangle.length;
    int[][] dp = new int[n][];
    dp[n - 1] = triangle[n - 1].clone();                    // base case: the last row costs itself
    for (int i = n - 2; i >= 0; i--) {
        dp[i] = new int[i + 1];
        for (int j = 0; j <= i; j++) {
            dp[i][j] = triangle[i][j] + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }
    return dp[0][0];
}

Complexity. Time O(n^2), space O(n^2).

Approach 4: Space optimized

Intuition. Row i only reads row i + 1, so keep a single array below holding the answers for the row underneath. Updating it in place, left to right, is safe here: the new below[j] needs the old below[j] and the old below[j + 1]. Position j + 1 has not been overwritten yet when we compute position j, and the old below[j] is read just before it is replaced. After processing row i, below[0..i] holds row i’s answers, and the leftover entries to the right are simply never read again.

This answers LeetCode’s follow-up of using only O(n) extra space.

Algorithm.

1. below = copy of the last row.
2. For i from n - 2 down to 0, for j from 0 to i: below[j] = triangle[i][j] + min(below[j], below[j + 1]).
3. Return below[0].

static int spaceOptimized(int[][] triangle) {
    int n = triangle.length;
    int[] below = triangle[n - 1].clone();
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            below[j] = triangle[i][j] + Math.min(below[j], below[j + 1]);  // below[j + 1] is not overwritten yet
        }
    }
    return below[0];
}

Dry run on Example 1:

The answer is below[0] = 11.

Complexity. Time O(n^2), space O(n).

Edge cases and pitfalls

• One row. The answer is the apex itself, including when it is negative.
• Negative values. They rule out -1 as a memo sentinel and make “take the smaller child” even less reliable.
• Direction of the loop. Going right to left in the in-place update would overwrite below[j + 1] before it is read. Left to right is the correct order for this recurrence.
• Top-down tabulation. Filling from the apex downward also works, but then each cell has one or two parents depending on whether it is on an edge, and the answer is the minimum of the last row. The bottom-up direction avoids both complications.
• Not modifying the input. The methods copy the last row with clone() instead of writing into triangle, so the caller’s data is unchanged.
• Testing. 200 seeded random triangles of up to 10 rows, with negative values, run through all four methods.

Related problems

• Minimum Falling Path Sum has a variable start as well as a variable end, and three moves per step.
• Minimum sum path in the matrix has fixed start and end cells on a rectangular grid.
• Grid Unique Paths : DP on Grids (DP8) counts paths instead of minimising their cost.
• Pascal’s Triangle I builds a triangle where each cell is computed from the two cells above it.