DSA & Algorithms
Part 19 of 21 · DSA Interview PatternsDynamic Programming — 1D Patterns — Climb, House Robber, LIS Families
1D DP templates: recurrence, rolling arrays, and classic climb/robber/LIS shapes.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The state is an index, and subproblems overlap
Prefer
One array, or a handful of rolling variables
Climbing stairs, house robber, coin change, and LIS are the same shape: define dp[i], write the recurrence, set the base.
- Robber: max(skip, take) with the previous two answers.
- Unbounded coins loop amount outside and coins inside.
- If only the last k states matter, do not store the whole array.
Alternative
Search every subset
Exponential, and it recomputes the same prefix over and over.
- A base case that is off by one.
- 0/1 loop order used on an unbounded problem.
- Calling it DP without saying what the cell means.
Define the cell, then fill left to right
The meaning of dp[i] is the sentence you say out loud.
- 1
Name dp[i]
Best answer on the prefix that ends at i, or uses the first i items. - 2
Write the jump
i-1, i-2, or any earlier j that is allowed. - 3
Roll if you can
Two variables for robber and stairs. The full row when you cannot.
Overview
1D DP templates: recurrence, rolling arrays, and classic climb/robber/LIS shapes.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use 1D DP when state is an index (and maybe a few flags), with recurrence over smaller indices.
Recognition cues
- climb stairs / fibonacci family
- house robber
- coin change (unbounded)
- longest increasing subsequence
- decode ways / word break
Mental model
Flow
- 1
1. State is an index i
- next2. Recur from earlier indexes
- 2
2. Recur from earlier indexes
- next3. Take max, min, or a count
- 3
3. Take max, min, or a count
- next4. Roll if only the tail matters
- 4
4. Roll if only the tail matters
Lesson map
Dynamic Programming — 1D Patterns — Climb, House Robber, LIS Families
1D DP templates: recurrence, rolling arrays, and classic climb/robber/LIS shapes.
Architecture. 1. State is an index i Ready. 2. Recur from earlier indexes Ready. 3. Take max, min, or a count Ready. 4. Roll if only the tail matters Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB I["1. State is an index i Ready"] Rec["2. Recur from earlier indexes Ready"] Opt["3. Take max, min, or a count Ready"] Roll["4. Roll if only the tail matters Ready"] I -->|continues| Rec Rec -->|continues| Opt Opt -->|continues| Roll
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Typical O(n * state) time; rolling O(state) space.
- LIS O(n^2) classic; O(n log n) with patience sorting follow-up.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Climbing Stairs
- House Robber
- House Robber II
- Coin Change
- Longest Increasing Subsequence
- Word Break
- Decode Ways
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
State meaning?
Answer
Always define dp[i] in one sentence before coding: best answer for prefix i (House Robber), LIS ending exactly at i, or whether prefix i can be segmented (Word Break).
Robber recurrence?
Answer
max(skip i = dp[i-1], take i = dp[i-2]+nums[i]).
Coin change loops?
Answer
Outer amount, inner coins for unbounded min coins.
LIS follow-up?
Answer
Patience sorting / binary search tails O(n log n).
Word break?
Answer
dp[i] true if some word ends at i and dp[start] true.
Space opt?
Answer
Keep only last few states if recurrence allows.