Triangle — Bottom-Up DP on a Variable-Width 2D Structure

Problem Statement#

Given a triangle array, return the minimum path sum from top to bottom. At each step you may move to an adjacent number of the row below. Adjacent numbers of element triangle[i][j] are triangle[i+1][j] and triangle[i+1][j+1].

Constraints:

• 1 <= triangle.length <= 200
• triangle[i].length == i + 1
• -10^4 <= triangle[i][j] <= 10^4

Example 1:

Input:  triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The path 2 -> 3 -> 5 -> 1 has sum 11.

Example 2:

Input:  triangle = [[-10]]
Output: -10

Example 3:

   [2]
  [3, 4]
 [6, 5, 7]
[4, 1, 8, 3]
Output: 11

Why This Problem Matters#

Triangle is one of the earliest DP problems in competitive programming history — it famously appears in the IOI and is a standard FAANG warm-up. It teaches a critical DP skill: working on non-rectangular 2D structures where row widths vary.

The top-down direction feels natural (start at the apex, pick cheapest child), but it forces you to scan the entire bottom row at the end to find the minimum. The bottom-up direction is more elegant: start from the last row and merge upward — by the time you reach the apex, it holds the global minimum with no extra scan needed.

Amazon and Microsoft use this problem to test whether candidates can choose optimal DP direction and whether they recognize the O(n) space optimization — work in the last row itself, overwriting it in place.

The Core Insight#

State definition (bottom-up): Let dp[j] be the minimum path sum from position j in the current row down to the base of the triangle.

Bottom row initialization: Each position in the last row represents a complete path of length 1 — no children below. dp = triangle[-1][:].

Upward recurrence: For each row from second-to-last up to the apex, and for each position j in that row:

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

Pick the cheaper of the two children directly below (j) and diagonally right (j+1).

Answer: After processing all rows upward, dp[0] holds the minimum path sum from apex to base.

Why bottom-up? Going upward means we never need to find the minimum across the base row afterward — the apex naturally accumulates the global optimal.

Building the DP Solution#

Step 1 — Top-down recursion (exponential):

def minimumTotal(triangle):
    def rec(i, j):
        if i == len(triangle):
            return 0
        return triangle[i][j] + min(rec(i+1, j), rec(i+1, j+1))
    return rec(0, 0)

Step 2 — Top-down with memoization:

from functools import lru_cache
 
def minimumTotal(triangle):
    n = len(triangle)
    @lru_cache(None)
    def dp(i, j):
        if i == n:
            return 0
        return triangle[i][j] + min(dp(i+1, j), dp(i+1, j+1))
    return dp(0, 0)

O(n^2) time and space where n is the number of rows.

Step 3 — Bottom-up with separate 1D dp:

def minimumTotal(triangle):
    n = len(triangle)
    dp = triangle[-1][:]  # copy last row
    for i in range(n-2, -1, -1):
        for j in range(i + 1):  # row i has i+1 elements
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    return dp[0]

Visual Dry Run#

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Initialize dp = last row:

dp = [4, 1, 8, 3]

Row i=2 (elements: 6, 5, 7):

• j=0: dp[0] = 6 + min(4, 1) = 7
• j=1: dp[1] = 5 + min(1, 8) = 6
• j=2: dp[2] = 7 + min(8, 3) = 10

dp = [7, 6, 10, ...]

Row i=1 (elements: 3, 4):

• j=0: dp[0] = 3 + min(7, 6) = 9
• j=1: dp[1] = 4 + min(6, 10) = 10

dp = [9, 10, ...]

Row i=0 (element: 2):

• j=0: dp[0] = 2 + min(9, 10) = 11

Answer: dp[0] = 11

Bottom-up DP table (one row per iteration):

Optimized Solution#

Python#

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        # Copy the last row — do not mutate the input
        dp = triangle[-1][:]
 
        # Work upward from second-to-last row to the apex
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(i + 1):  # row i has exactly i+1 positions
                # Add current cell's value to the cheaper child below
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
 
        # Apex now holds the global minimum path sum
        return dp[0]

JavaScript#

var minimumTotal = function(triangle) {
    const n = triangle.length;
 
    // Spread copies the last row — avoids mutating input
    const dp = [...triangle[n - 1]];
 
    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
        }
    }
 
    return dp[0];
};

Complexity Analysis#

Where n is the number of rows and total elements are n*(n+1)/2.

Common Mistakes#

1. Going top-down and forgetting to scan the last row for the minimum. Top-down DP fills from apex to base. After the fill, you must scan the entire last row to find the global minimum — an extra O(n) step that bottom-up avoids entirely.

2. Iterating past the row boundary. Row i has exactly i+1 elements. The inner loop must be range(i+1) — not range(len(triangle[i])) which would work but is less idiomatic, and not range(i+2) which reads past the end.

3. Taking a reference instead of copying the last row. dp = triangle[-1] is a reference — modifying dp[j] destroys the original data. Use dp = triangle[-1][:] for an independent copy.

4. Confusing the children indices. For position j in row i, the two children in row i+1 are at j and j+1. Many candidates write j-1 and j by analogy with left/right in a grid — wrong for Triangle's structure.

5. Traversing rows in the wrong direction. The outer loop must go from n-2 down to 0 (upward). Accidentally going from 0 to n-2 (downward) produces top-down behavior with no memoization, giving wrong results.

Interview Tips#

• Lead with the direction choice: "I prefer bottom-up because after processing all rows, dp[0] is the answer — no extra minimum scan over the base row."
• Explicitly state range(i+1) for the inner loop when writing code — interviewers watch for this.
• Draw the triangle on paper first and label the children: j and j+1 (not j-1 and j).
• Offer both approaches: "Top-down memoization also works in O(n^2) time but needs an extra scan at the end. Bottom-up is cleaner."
• For the in-place variant: "I can write into triangle[-1] directly for O(1) extra space, but that modifies the input — worth confirming with the interviewer."

Follow-up Questions#

Q: How do you reconstruct the minimum path? Save the full 2D bottom-up DP table (not just the 1D rolling dp). Starting from dp[0][0], at each row i choose the child dp[i+1][j] or dp[i+1][j+1] with the smaller value. Record the column indices.

Q: What if you need the maximum path sum instead? Replace min with max everywhere. The structure is identical — same recurrence, same direction, same complexity.

Q: What if movement can skip rows? Add a new dimension to the state: dp[i][j] = min cost reaching (i,j) from the apex, with transitions from all valid sources. This is no longer a pure triangle problem but a general DAG shortest path.

Q: How does Triangle compare to Minimum Path Sum? Minimum Path Sum uses a rectangular m x n grid; Triangle has a variable-width grid where row i has i+1 elements. Both use dp[j] = cell + min(above, left-child) semantics, but Triangle's "left" and "right" children are indexed differently (j and j+1 below vs. j-1 and j-1+1 in a rectangle).

Key Takeaways#

• Bottom-up triangle DP (dp = triangle[-1][:] then merge upward) gives dp[0] as the answer directly — no post-scan needed.
• The recurrence dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) must be applied from second-to-last row up to the apex.
• Row i has exactly i+1 elements — always use range(i+1) for the inner loop, never go to i+2.
• Use [:] to copy the last row; avoid reference aliasing that silently mutates the input.
• The "children are at j and j+1" rule differs from rectangular grids where neighbors are (i-1, j) and (i, j-1) — draw the triangle before coding.
• Amazon and Microsoft use Triangle to probe DP direction intuition. Know both top-down and bottom-up, and explain why bottom-up is preferable for this specific problem.