When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Linear decisions with overlapping subproblems
- Take-or-skip recurrence
When another approach fits better
- A local greedy choice has a proof
- Every distinct solution must be enumerated rather than summarized
How it works#
Recursively try every decision sequence, recomputing identical suffixes many times.
Define one state in a sentence.
Write the recurrence from the last decision.
Set base cases, choose a dependency-respecting order, then compress space only if overwritten states are no longer needed.
Invariantdp[i] has one precise meaning for the first i items or state i, and every transition reads only already-correct dependency states.
Example and template#
House Robber
Define the best result up to each position using take-or-skip.
Open the full problem brief- State i
dp[i] = best for prefix ending before iThe definition excludes unresolved future choices.
- Transition
max(dp[i−1], value[i−1]+dp[i−2])The last choice is skip or take, and take excludes its neighbor.
dp[base states] = known values
for i in dependency order:
dp[i] = best_or_count(transition from prior states)
return dp[target]- Time
- O(number of states × transition work)
- Space
- O(number of stored states)
- Assumptions
- Each state is evaluated once and dependencies are already available in iteration order.
Pitfalls#
Common wrong approaches
A formula without a state definition often mismatches indexing or constraints.
Overwriting a dependency before the recurrence is proven creates subtle errors.
Edge cases
- Zero items
- One item
- Negative values and whether choosing none is allowed
- Unreachable states
Interview narration
- “The brute force revisits the same best suffix after different earlier paths.”
- “dp[i] means the best answer using the first i items.”
- “The final decision is either skip item i−1 or take it and combine with dp[i−2].”
Practice#
House Robber
Define the best result up to each position using take-or-skip.
Practice this problemCount ways to reach step n using one- or two-step moves.
Reveal the pattern decision
Use 1-D DP because state n depends only on counts for n−1 and n−2; there is no need to enumerate paths.
Transfer problem
Find the minimum cost to reach the end when each move advances one or two positions.
Checkpoint: Change the aggregation from count/sum to minimum while preserving the state definition and bases.
Follow-up variations
- Reconstruct the chosen items
- Compress to constant space and state which prior values remain live
Error-log prompts
- Could I say dp[i] without code?
- Did iteration order make every dependency ready?