Lowest Descent of the Pyramid
Medium2-D Dynamic Programming
Problem
A pyramid of numbered stones is given as pyramid, where row r (0-indexed) holds r + 1 integers. A climber starts on the single stone at the top and walks down one row at a time. From position j in a row she may step to position j or j + 1 in the row below.
The cost of a descent is the sum of the stones she stands on, from the top row to the bottom row. Stones may carry negative numbers. Return the minimum possible cost.
Example 1
- Input:
- pyramid = [[3], [6, 4], [5, 1, 8], [2, 7, 3, 9]]
- Output:
- 11
3 → 4 → 1 → 3 costs 11. The tempting 6 on the left would lead to at least 3 + 6 + 1 + 3 = 13.
Example 2
- Input:
- pyramid = [[-4]]
- Output:
- -4
Constraints
- 1 ≤ pyramid.length ≤ 200
- pyramid[r].length == r + 1
- -10^4 ≤ pyramid[r][j] ≤ 10^4
Hint
Show the first hint
Going top-down, the best cost into a stone depends on two parents, and the edges of each row have only one. Is there a direction with fewer special cases?
Walkthrough
How to approach it
01Clarify before coding
- Can values be negative? Yes, so you cannot prune a descent early just because its running sum is large.
- Must the descent reach the bottom row? Yes, every descent visits exactly one stone per row.
- Is the input guaranteed to be a proper triangle? Yes, row r has r + 1 entries.
02Brute force
Try every descent: at each of the n - 1 steps choose left or right, and sum the stones.
Cost: O(2^(n-1) · n) time; for 200 rows that is about 10^60 descents.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.