Pattern visualizer
Triangle
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. 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..
In-place fold: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1]), bottom row up
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