Triangle
In-place fold: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1]), bottom row up
Reading the triangle top-down means every edge cell needs a bounds check (the leftmost and rightmost cells of a row have only one neighbor above, not two) and the final answer needs a scan across the whole bottom row. Turn it upside down instead: the bottom row already IS its own minimum path sum, with nothing below to choose between. Fold that row into the one above by replacing each cell with itself plus the cheaper of its two children, and repeat upward. No edges to special-case, and the answer always lands on exactly one cell — the apex.
Details
Animated on: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] — from the top, move to an adjacent number on the row below at each step; find the minimum path sum to the bottom.
Problem:TriangleMedium
In-place fold: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1]), bottom row up
step 1 / 8
dp — the minimum path sum from (r, c) to the bottom
The bottom row (row 3) needs no folding: with nothing beneath it, each cell's own value is already its minimum path sum to the bottom.
1FUNCTION minimumTotal(triangle):2 n <- LENGTH(triangle)3 dp <- COPY(triangle)4 FOR r FROM n - 2 DOWNTO 0:5 FOR c FROM 0 TO r:6 dp[r][c] <- dp[r][c] + MIN(dp[r+1][c], dp[r+1][c+1])7 RETURN dp[0][0]
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- The bottom row (row 3) needs no folding: with nothing beneath it, each cell's own value is already its minimum path sum to the bottom.
- (2,0) can only step down to (3,0)=4 or (3,1)=1, so it folds in the cheaper one: 6 + min(4, 1) = 7.
- (2,1) can only step down to (3,1)=1 or (3,2)=8, so it folds in the cheaper one: 5 + min(1, 8) = 6.
- (2,2) can only step down to (3,2)=8 or (3,3)=3, so it folds in the cheaper one: 7 + min(8, 3) = 10.
- (1,0) can only step down to (2,0)=7 or (2,1)=6, so it folds in the cheaper one: 3 + min(7, 6) = 9.
- (1,1) can only step down to (2,1)=6 or (2,2)=10, so it folds in the cheaper one: 4 + min(6, 10) = 10.
- (0,0) can only step down to (1,0)=9 or (1,1)=10, so it folds in the cheaper one: 2 + min(9, 10) = 11.
- Every row has folded into the one above it, so dp[0][0] = 11 is now the minimum path sum for the whole triangle, top to bottom.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.