Advanced · Module 18 · Lesson 2
1D DP
Fibonacci, climbing stairs, robber, and state compression.
15–25 min readLesson 106 of 123
Lesson 106 of 123
1d streakTheory lesson · Step-by-step
Understand 1D DP
Fibonacci, climbing stairs, robber, and state compression.
Worked approach
Trace the reasoning step by step
- 1Define the minimal state variables needed by 1D DP.
- 2Write the recurrence as choices from smaller states.
- 3Set base cases for the smallest reachable states.
- 4Choose memoization or an evaluation order in which dependencies are ready.
- 5Return the requested state, then optimize memory only if dependency order permits.
Concrete example
Maximize non-adjacent sum of [2,7,9,3,1].
- 1At each index choose skip or take plus dp[i−2].
- 2Best values progress 2,7,11,11,12.
Maximum is 12.
What must remain true (Loop Invariant)
Every state consumed by 1D DP already stores the correct answer for its declared subproblem, so each transition uses only valid dependencies.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Linear state scan
O(n)
O(1) to O(n)
The bound follows from the number of states visited and the work performed per transition.When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked 1D DP example without looking at the trace.
- Change one input condition and explain whether the 1D DP invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.