#120
Triangle
Medium Bottom-up DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the minimum path sum from the top to the bottom of a number triangle, moving to an adjacent number on the row below each step.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the smallest top-to-bottom path sum in a triangle.
Why this works: go bottom-up: each cell becomes its value + the smaller of its two children.
Example: [[2],[3,4],[6,5,7],[4,1,8,3]]
row 2 becomes [7, 6, 10]row 1 becomes [9, 10]top 2 + 9 = 11
✦Hints open one at a time
Going top-down needs care at the edges. Go bottom-up instead.
best[i] on a row = value + min(best[i], best[i + 1]) of the row below.
↗Approach
Start with a copy of the last row. Move up row by row, updating in place. The answer ends in best[0].
</>Solution (Java)
import java.util.*;
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] best = new int[n + 1]; // row below the last row = zeros
for (int r = n - 1; r >= 0; r--) {
for (int i = 0; i <= r; i++) {
best[i] = triangle.get(r).get(i) + Math.min(best[i], best[i + 1]);
}
}
return best[0];
}
}!Common mistake
Greedily picking the smaller child at each step.
Complexity
- Time: O(n²) for n rows.
- Space: O(n).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon