AdvancedDynamic Programming
Most 1-D DP needs only two variables
If dp[i] only looks back one or two steps, you don't need the whole array: keep two variables and roll them forward.
The idea
In Climbing Stairs and House Robber, each entry depends only on the previous one or two. Everything older is never read again, so an array of n entries is wasted space.
Keep the last two values and shift them each step. Same time, O(1) space.
Worked example
Climbing Stairs, n = 5 (ways to climb with 1 or 2 steps)
- ways(1)=1, ways(2)=2
- ways(3)=3, ways(4)=5, ways(5)=8: each is the sum of the previous two.
In code (Python)
def climb_stairs(n):
one_back, two_back = 1, 1 # ways(i-1), ways(i-2)
for _ in range(n - 1):
one_back, two_back = one_back + two_back, one_back
return one_back
def rob(nums):
take_prev = skip_prev = 0
for x in nums:
take_prev, skip_prev = skip_prev + x, max(take_prev, skip_prev)
return max(take_prev, skip_prev)O(n) time, O(1) space.
How to spot it
- Any recurrence that only reaches back a fixed number of steps.
Common mistakes
- Updating one variable before the other reads its old value: use tuple assignment or a temp.
- Optimizing before the plain array version is correct.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →