DSA AnimatorDSA animations
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.

How to solve Triangle

LeetCode 120 · Medium · Dynamic Programming · Pattern: Bottom-Up DP

Why the obvious approach is slow

Trying every top to bottom path doubles the work with every row. There are 2 to the power of the height of paths.

The key idea

Work from the bottom row upwards. Start with a copy of the last row, which is the best cost from each bottom position. For each number above, add the smaller of its two children below. Each row shrinks by one, and after the top row, a single value is left. That value is the minimum path sum.

Remember

Bottom up removes all the edge cases of top down. Each cell picks the better of its two children.

Run the animation above on your own input, or watch the 1:45 video explanation of Triangle with a dry run and Java code.

More Dynamic Programming problems