Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: Stair Memories.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when One-dimensional dynamic programming matches the clues
- 2Keep this true after every move: previous states hold the exact number of ways to reach their stairs
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: previous states hold the exact number of ways to reach their stairs
Lesson 1 of 3
Live algorithm trace
One-dimensional dynamic programming
Complete execution1 of 6
Base cases say there is one way to stand before climbing and one way to reach stair 1.
1
one, two = 1, 12
for each stair3
one, two = one + two, one4
return onen = 5one = 1two = 1
Truth to preserve / Cost target
Truth to preserve
previous states hold the exact number of ways to reach their stairs
Cost target
O(n)
Dynamic programming names a state and reuses solved smaller states. To reach a stair, the last move came from one or two stairs below.
Your call · What should guide every step of this algorithm?