• 1 ≤ triangle.length ≤ 200
• triangle[i].length == i + 1
• -10⁴ ≤ triangle[i][j] ≤ 10⁴
• From index j you may step to index j or j + 1 in the next row

Draw the triangle left-aligned and the rule becomes obvious:

      [2]
     [3, 4]
    [6, 5, 7]
   [4, 1, 8, 3]

Standing at index j of row i, the two numbers directly below you are index j and index j+1 of row i+1. That is it. You cannot jump sideways, you cannot skip a row, and you always end up somewhere in the last row.

An immediate consequence worth stating: every path visits exactly one number per row, so all paths have the same length. We are choosing which numbers, not how many.

Also note the values may be negative. That rules out any argument of the form "stop early because the sum can only grow" — a bad-looking start can be rescued by a large negative later, so every path must be considered on its full merits.

The obvious greedy rule: at each row, step onto whichever of the two numbers below is smaller. Run it on the triangle above. From 2, the choices are 3 and 4, so take 3. From 3, the choices are 6 and 5, so take 5. From 5, the choices are 1 and 8, so take 1. Total: 2 + 3 + 5 + 1 = 11.

That happens to be the right answer for this triangle, which is exactly why the rule is dangerous — it looks confirmed. Change one number: make the bottom row [4, 100, 8, 3]. Greedy still walks 2, 3, 5 and is then forced onto 100 or 8, giving at best 18. Meanwhile the route 2 → 4 → 7 → 3 totals 16.

The failure is structural and by now familiar: a small number now can lead you into a region where everything is large. The only honest fix is to compare the best possible completion of each choice, which is what the recurrence does.

Brute force would try every path, and since each of the n-1 steps branches in two, that is 2ⁿ⁻¹ paths — around 10⁶⁰ for a 200-row triangle.

Where you are is a row and an index within it. What you do next depends on nothing else — not on which numbers you already collected, only on where you are standing.

Two moves, take the better completion:

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

Base case: on the last row there is nowhere to go, so f(last, j) = triangle[last][j].

The answer is f(0, 0).

Notice the direction: this state is defined from a cell down to the bottom, not from the top down to a cell. You can set up a path problem either way. Here the downward version is easier, because the base case becomes a whole known row — the bottom row itself — instead of a single corner. Whichever you pick, state it precisely and make the recurrence match.

def minimum_total(triangle):
    n = len(triangle)
    memo = {}

    def f(i, j):
        if i == n - 1: return triangle[i][j]
        if (i, j) in memo: return memo[(i, j)]
        memo[(i, j)] = triangle[i][j] + min(f(i + 1, j), f(i + 1, j + 1))
        return memo[(i, j)]

    return f(0, 0)

There is one state per cell, so O(N²) time.

Now the table. Let dp[i][j] hold what f(i, j) returned, and swap calls for reads:

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

Each cell reads the row i+1 below it, so fill bottom to top. The base case copies from the recursion: the last row has no row below, so dp[last][j] = triangle[last][j] — start the table as a copy of the bottom row. The answer is dp[0][0]:

def minimum_total(triangle):
    n = len(triangle)
    dp = [row[:] for row in triangle]        # copy; last row is already the base case

    for i in range(n - 2, -1, -1):
        for j in range(i + 1):               # row i has exactly i+1 entries
            dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1])

    return dp[0][0]

The inner bound range(i + 1) is the only thing that distinguishes a triangle from a rectangle. Because row i is one shorter than row i+1, the index j+1 is always valid — there is never a boundary check to write. That is a pleasant consequence of working bottom-up here; had we filled top-down instead, the edges of each row would each have only one parent and would need special handling.

Each row only ever reads the row directly below it, so keep a single array of size n and overwrite it in place, sweeping j upward:

def minimum_total(triangle):
    dp = triangle[-1][:]                     # start as the bottom row
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(i + 1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

Sweeping j from left to right is safe here even though we overwrite in place, because computing dp[j] reads dp[j] and dp[j+1], both of which are still the lower row's values at that moment — we only ever destroy entries we have already passed. O(N) space.

Row 2 [6, 5, 7]:
- 6 + min(4, 1) = 6 + 1 = 7
- 5 + min(1, 8) = 5 + 1 = 6
- 7 + min(8, 3) = 7 + 3 = 10
→ [7, 6, 10]

Row 1 [3, 4]:
- 3 + min(7, 6) = 3 + 6 = 9
- 4 + min(6, 10) = 4 + 6 = 10
→ [9, 10]

Row 0 [2]:
- 2 + min(9, 10) = 2 + 9 = 11

Answer 11, along 2 → 3 → 5 → 1.

Now the modified triangle with bottom row [4, 100, 8, 3], where greedy failed:

The table finds 15, better than both the greedy 18 and the 16 route we spotted by eye — a good reminder that the eye is not a reliable optimiser either.

This problem is a clean demonstration of a choice you make on every one of these tables: which direction to define your state in. "Best from here to the end" and "best from the start to here" are both valid, and they lead to different loop directions and different base cases. Pick whichever makes the base case simpler to write down. For a triangle, the bottom row is a whole row of trivially known answers, so working upward is the natural fit.

The other transferable point is the shape of the counterexample that killed greedy: a locally attractive step commits you to a region you would rather have avoided. Get in the habit of actively hunting for that shape before trusting any greedy rule — one counterexample is faster to find than a proof, and it settles the matter for good.