TL;DR
Bottom-up DP collapsing each row into a 1-D array — O(n²) time (n² cells), O(n) space.
Approach 1 — Brute-force recursion
From the top, try both downward steps at every cell and keep the cheaper total. Each cell (i, j) reaches exactly two cells below it, (i+1, j) and (i+1, j+1):
graph TD
A["2"] --> B["3"]
A --> C["4"]
B --> D["6"]
B --> E["5"]
C --> E
C --> F["7"]
D --> G["4"]
D --> H["1"]
E --> H
E --> I["8"]
F --> I
F --> J["3"]
The minimum path here is 2 → 3 → 5 → 1 = 11.
Recurrence: best(i, j) = triangle[i][j] + min(best(i+1, j), best(i+1, j+1)). Base: on the last row, best(i, j) = triangle[i][j].
def minimumTotal(triangle: list[list[int]]) -> int:
n = len(triangle)
def best(i: int, j: int) -> int:
if i == n - 1:
return triangle[i][j]
below = min(best(i + 1, j), best(i + 1, j + 1))
return triangle[i][j] + below
return best(0, 0)
Complexity: each cell spawns two calls and cells are recomputed → O(2ⁿ) time, which is infeasible at n = 200.
Approach 2 — Memoized top-down
best(i, j) depends only on (i, j), and there are 1 + 2 + ... + n = O(n²) such cells. Cache each result so it is computed once.
from functools import lru_cache
def minimumTotal(triangle: list[list[int]]) -> int:
n = len(triangle)
@lru_cache(maxsize=None)
def best(i: int, j: int) -> int:
if i == n - 1:
return triangle[i][j]
return triangle[i][j] + min(best(i + 1, j), best(i + 1, j + 1))
return best(0, 0)
Complexity: O(n²) time and space (one entry per cell, plus recursion stack).
Approach 3 — Tabulated bottom-up (2-D)
Build a dp grid where dp[i][j] is the min path sum from (i, j) to the bottom. Seed the last row from the triangle, then fill upward.
def minimumTotal(triangle: list[list[int]]) -> int:
n = len(triangle)
dp = [row[:] for row in triangle] # copy so we don't mutate input
for i in range(n - 2, -1, -1):
for j in range(i + 1):
dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1])
return dp[0][0]
Complexity: O(n²) time, O(n²) space.
Approach 4 — Space-optimized 1-D (the intended solution)
Filling bottom-up, row i reads only row i+1. Keep a single array dp of length n initialized to the bottom row; each higher row overwrites it in place, left to right. Each dp[j] uses the old dp[j] and dp[j+1], both still valid before this cell is written.
def minimumTotal(triangle: list[list[int]]) -> int:
dp = triangle[-1][:] # start from 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]
Walkthrough (triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]):
- start
dp = [4,1,8,3]
- row
[6,5,7]: dp[0]=6+min(4,1)=7, dp[1]=5+min(1,8)=6, dp[2]=7+min(8,3)=10 → dp=[7,6,10,3]
- row
[3,4]: dp[0]=3+min(7,6)=9, dp[1]=4+min(6,10)=10 → dp=[9,10,...]
- row
[2]: dp[0]=2+min(9,10)=11 → dp[0]=11
Complexity: O(n²) time, O(n) space — meeting the follow-up.
Common pitfalls
- Going top-down in the tabulation and mishandling the edges (the leftmost and rightmost cells of each row have only one valid parent above). Bottom-up sidesteps this entirely — every interior cell has both children present.
- Overwriting the 1-D array right-to-left, which corrupts the
dp[j+1] you still need; go left-to-right in the bottom-up scheme above.
- Mutating the input
triangle in place when the caller may reuse it — copy the bottom row.
- Assuming values are non-negative: entries can be negative, so a greedy “always pick the smaller next cell” fails; only the DP is correct.
Pattern takeaway
Grid/triangle path-sum problems reduce to “this cell’s best = its value + best of the cells it can reach.” Compute it bottom-up so every dependency is ready and the edge cases vanish, then compress the DP table to a single row whenever each row only reads its immediate neighbor row — the standard 2-D-to-1-D space optimization.