← Back to DSA Animator
Triangle LC #120 Medium DP · Bottom-Up
Problem

Find the minimum path sum from top to bottom of a triangle. At each step you move to an adjacent number in the row below (index i or i+1).

Example
[[2],[3,4],[6,5,7],[4,1,8,3]] → 11 (path 2→3→5→1)
Constraints: 1 ≤ rows ≤ 200
Try Examples
Custom:
Approach
Bottom-Up DP — Start from Last Row
dp[c] = min path from (r,c) to bottom. dp[c] = triangle[r][c] + min(dp[c], dp[c+1]). Process rows upward.
Triangle & DP
Load an example.
Variables
row r, col c
—
left (dp[c])
—
right (dp[c+1])
—
answer
—
Step Logic
Press ▶ Play or Next Step to begin.
📍
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Init dp with bottom row values
2
For r from second-last to 0: dp[c] = t[r][c] + min(dp[c], dp[c+1])
3
Return dp[0]
Time
O(n²)
Space
O(n)
Why This Works

Bottom-up: start at the last row. Each cell picks the smaller of its two children below. After processing all rows, dp[0] holds the minimum path sum from top to bottom.