Linear DP
What is this?
Linear DP is the simplest flavor of dynamic programming: you walk along a single line — an array, a string, or a number — and each answer dp[i] is built from one or two answers you already worked out just before it. It is exactly like figuring out the cheapest way to reach step i on a staircase once you know the cheapest way to reach the steps below. Because each small answer is reused many times, you store it once instead of recomputing it.
💡 Fun fact: The "counting bits" idea — that the number of 1-bits in
iequals the bits iniwith its last bit removed, plus that last bit — is so cheap that modern CPUs ship a singlepopcountinstruction to do it in hardware.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Dynamic programming is just remembering the answers to overlapping subproblems instead of recomputing them. Linear DP is where you learn the method on a single axis:
dp[i]answers a question about the firstielements (or the numberi), and the recurrence buildsdp[i]from a few earlier entries. Master the 4-step method here and every harder DP is a variation.
The 4-step DP method
![The 4-step DP method: 1 Subproblem (what does dp[i] mean), 2 Recurrence (how dp[i] uses earlier dp[]), 3 Base cases (the smallest subproblems), 4 Optimize (table to rolling variables, O(1) space)](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/dynamic-programming/linear-dp/linear-dp-summary-diagram-1.svg)
Every lesson here is the same recurrence expressed four ways — brute recursion, memoized top-down, bottom-up table, and rolling variables. They differ only in what they remember and when.
The problems
![Linear DP family tree: dp[i] from earlier entries branches into Min Cost Climbing Stairs (the intro), Word Break (DP over a string prefix), Rotated Digits (state from a sub-number), and Counting Bits (DP riding on bit structure)](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/dynamic-programming/linear-dp/linear-dp-summary-diagram-2.svg)
- Min Cost Climbing Stairs — the gentle intro:
dp[i] = cost[i] + min(dp[i-1], dp[i-2]); the place to learn the whole method. - Word Break —
dp[i]= "is the prefixs[:i]segmentable?"; break at the last word. - Rotated Digits — a number's verdict composes from
dp[i//10]plus its last digit. - Counting Bits —
dp[i] = dp[i>>1] + (i&1): every number reuses a smaller solved one.
Key takeaways
- DP = overlapping subproblems + optimal substructure — remember, don't recompute.
- The recurrence is the whole game; the four implementations just trade memory for clarity.
dp[i]over a prefix is the linear template — a string, an array, or a number.- Optimize last — once the table works, keep only the few entries the recurrence reads.
- Why interviewers love it: it reveals whether you can define a subproblem and a transition, the core DP skill.
Start here: Min Cost Climbing Stairs (learn the method), then Word Break.
Core idea: a number is good when (1) none of its digits is invalid under a 180° rotation, and (2) at least one digit actually changes when rotated. Both conditions are decided digit-by-digit, which means the answer for a number composes from the answer for the number with its last digit removed — a quietly linear DP.
Problem, rephrased
Picture writing a number on a slip of paper, then physically turning the slip upside down (rotate it 180°). Each digit lands on top of where the last digit was — the order reverses — but for counting purposes we only care about one thing per digit: what does this glyph become?
0,1,8rotate to themselves (a0upside down is still a0).2 ↔ 5and6 ↔ 9rotate to a different valid digit (a6flipped is a9).3,4,7become garbage — no valid digit, the whole number is ruined.
A number x is good when, after flipping every digit, you still have a valid number and that new number is different from x. "Different" is the trap: 8 flips to 8, so 8 is not good (it didn't change). But 2 flips to 5, so 2 is good.
Given n, count how many integers in [1, n] are good.
n |
Good numbers in [1, n] |
Count |
|---|---|---|
1 |
(1 is self-only → not good) |
0 |
2 |
2 |
1 |
10 |
2, 5, 6, 9 |
4 |
20 |
2, 5, 6, 9, 12, 15, 16, 19, 20 |
9 |
Look at n = 10: the four good numbers are exactly the single digits that change (2, 5, 6, 9). 1 and 8 are valid but unchanged (not good); 10 contains a 1 and a 0, both unchanged, so 10 itself is not good.
The n = 20 row is worth studying because of what's missing from it. 18 looks plausible — both digits are valid — but it flips digit-wise to 18, unchanged, so it's excluded. 13, 14, 17 are out for containing the invalid digits 3, 4, 7. Meanwhile 20 makes the cut: the 2 changes (to 5) and the 0 is a harmless self-digit. The verified count is 9, and the runnable code at the bottom is the source of truth — trust it over hand-counting.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson