DP — 1-D sequences
📖 Walk me through it — plain English
Dynamic programming (DP) just means: solve a problem by building up answers to smaller versions of it and reusing them, instead of recomputing the same thing over and over. "1-D" here means the smaller problems are lined up in a single row — one answer per position i as we walk left to right through an array. We keep a table (or just a couple of variables) called dp, where dp[i] is "the best answer using everything up to position i." The whole skill is writing one sentence for what dp[i] means, then a formula (the recurrence) that builds dp[i] from a few earlier cells.
The lesson's worked template is House Robber: houses sit in a row, each holds some money, and you cannot rob two adjacent houses (alarms go off). Maximize the loot. The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). In words: at each house you face one of two choices — skip this house and keep whatever was best up to the previous house (dp[i-1]), or rob this house, which forces you to skip its neighbor, so you add this house's money to the best total from two houses back (dp[i-2] + nums[i]). Take whichever is larger.
The everyday analogy: you're walking down a street of houses with a sack. At each door you make a snap decision — "grab this one (and I had to have skipped the last door), or walk past it and keep what I already had." You never need the whole street in memory; you only need to remember your best total at the last door and at the door before that. Those are the two rolling variables prev1 (= dp[i-1]) and prev2 (= dp[i-2]) in the template.
Let's trace it on a tiny street, nums = [2, 7, 9, 3]. We start with both rolling totals at 0 (no houses robbed yet). The accent (highlighted) cell is the house we're deciding on right now; cells before it are already decided.
Why it works: at every house, the only thing that matters for future decisions is "what's the best I could have done if I stop here" and "...if I stop one house earlier." Every choice depends only on those two numbers, so once we slide past a house we never need it again — that's why two variables replace the whole table. Why it's fast: we touch each house exactly once and do a single comparison, so it's O(n) time (work grows in proportion to the number of houses) and O(1) space (a fixed two variables, no matter how long the street). The clever line prev2, prev1 = prev1, max(prev1, prev2 + n) does both updates at once: the right side is computed first using the old values, then both are reassigned, so prev2 correctly becomes the old prev1 while prev1 becomes the new best.
The simplest DP family has a state indexed by a single position i walking left to right through an array or string. The answer at i is built from a constant number of earlier answers — almost always dp[i-1] and dp[i-2]. The anchor everyone starts with is Climbing Stairs: to reach step i you either took a single step from i-1 or a double step from i-2, so the number of ways is dp[i] = dp[i-1] + dp[i-2] — Fibonacci in disguise. Run the same 4-step recipe every time: (1) define what dp[i] means in one sentence, (2) write the recurrence relating it to smaller i, (3) nail the base cases, (4) pick an evaluation order so every dependency is computed first (left to right here). Because each cell looks back only a fixed distance, you can throw away the full table and keep one or two rolling variables — that is the O(1)-space trick the interviewer wants to see.
- "Number of ways" / "min cost" over a linear sequence
- Each step is a small local choice: take / skip / step by 1 or 2
- Answer at i depends only on a few earlier positions
- Greedy looks tempting but a local-optimal pick can be wrong
- "Can this string be segmented?" (Word Break) — DP over prefixes
- Longest / max contiguous-or-subsequence quantity
- Climbing Stairs — dp[i]=dp[i-1]+dp[i-2]
- House Robber I — dp[i]=max(dp[i-1], dp[i-2]+nums[i])
- House Robber II — circular: two linear runs
- Coin Change — fewest coins, dp[a]=min(dp[a-c])+1
- Word Break — dp[i] = some split j with dp[j] and s[j:i] in dict
- LIS — O(n²) dp, or O(n log n) tails
- Kadane — max subarray ending at i
def rob_line(nums):
# dp[i] = best loot from houses 0..i; carry only two rolling cells
prev2, prev1 = 0, 0 # prev2 = dp[i-2], prev1 = dp[i-1]
for n in nums:
prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1
def rob_circular(nums):
# House Robber II: first and last are adjacent on a circle.
# Either exclude the first house OR exclude the last; take the better.
if len(nums) == 1:
return nums[0]
return max(rob_line(nums[1:]), rob_line(nums[:-1]))
import bisect
def length_of_lis(nums):
# tails[k] = smallest possible tail of an increasing subseq of length k+1.
# NOTE: tails is NOT the subsequence itself, only its length is real.
tails = []
for x in nums:
i = bisect.bisect_left(tails, x) # strict increase; use bisect_right for non-strict
if i == len(tails):
tails.append(x) # x extends the longest run
else:
tails[i] = x # x replaces a tail, keeping it minimal
return len(tails) # O(n log n)function robLine(nums: number[]): number {
let prev2 = 0, prev1 = 0; // dp[i-2], dp[i-1]
for (const n of nums) {
const cur = Math.max(prev1, prev2 + n);
prev2 = prev1; prev1 = cur;
}
return prev1;
}
function lengthOfLIS(nums: number[]): number {
const tails: number[] = []; // tails[k] = min tail of length k+1
for (const x of nums) {
let lo = 0, hi = tails.length; // lower_bound (strict)
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
if (lo === tails.length) tails.push(x);
else tails[lo] = x;
}
return tails.length;
}- LIS, O(n²): dp[i] = length of longest increasing subseq ending at i; dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i]; answer is max(dp). The O(n log n) tails method gives only the length faster.
- Kadane (max subarray): cur = max(nums[i], cur + nums[i]) — extend the running sum or restart at i; track best = max(best, cur). Contiguous, so it is one rolling variable, not a table scan.
- Word Break: dp[i] = can s[0:i] be segmented; dp[i] = any(dp[j] and s[j:i] in words) for j < i. Put the dictionary in a set for O(1) lookups.
- Climbing Stairs / House Robber / Kadane: O(n) time, O(1) space with rolling vars.
- Coin Change: O(amount × coins) time, O(amount) space; init dp = [inf]*(amount+1), dp[0]=0, return -1 if dp[amount] stays infinite.
- LIS: O(n²) dp vs O(n log n) tails + binary search; bisect_left for strictly increasing, bisect_right if equal values are allowed.
- Base cases bite: empty input, single element. Climbing Stairs needs dp[0]=dp[1]=1; the rolling-var form starts both seeds at the right value.
- House Robber II: a circle means house 0 and house n-1 are adjacent — solve two linear sub-runs (exclude first, exclude last) and take the max; handle the single-house case before slicing.
- LIS tails is a witness, not the answer: the array holds minimal tails per length, so its contents are not a valid subsequence — only len(tails) is meaningful.
Write the canonical 1-D DP with two rolling variables — run it live: