1D Dynamic Programming

The 10-second versionCopy Anchor Link

A 1D DP is dynamic programming where the state is a single index — a position in a sequence — and the answer for each position depends only on a fixed handful of earlier positions. Almost every one of these problems yields to the same three-line recipe: define the state (what does dp[i] mean?), write the recurrence (how does dp[i] build from earlier states?), and set the base cases (the smallest states, filled by hand). Once you've written those three lines, the table fills itself — and very often, when each cell only needs the last one or two, you can collapse the whole O(n) table down to O(1) variables.

Why this existedCopy Anchor Link

One-dimensional recurrences are older than computers. In 1202, Leonardo of Pisa (Leonardo Fibonacci) published Liber Abaci, and with it the rabbit-breeding sequence that carried his name: each month's population is the last two months' populations added together. That's fib(n) = fib(n − 1) + fib(n − 2) — the original 1D DP, written down seven centuries before anyone had a machine to run it.

• 1202 — Fibonacci's rabbit problem: the first recurrence over a single index.
• 1957 — Bellman's Principle of Optimality turns "recurrence over a sequence" into a method: define the state, order the subproblems, fill them in.
• 1984 — Jay Kadane (in a problem posed by Ulf Grenander, and written up by Jon Bentley) gives the O(n) maximum-subarray scan — a single running state that recomputes in one pass what looked like an O(n²) problem.
• 1990s–2000s — three small problems — climbing stairs, house robber, and coin change — become the canonical teaching trio, because between them they cover every 1D DP idea: sum-of-two, max-of-two, and min-over-all-predecessors.

Why it mattered: sequences are everywhere — prices over time, messages on a wire, steps up a staircase — and the questions you ask of them ("best total so far?" "fewest coins?") almost always reduce to "the answer at position i is a small function of the answers just before it." Once that shape is visible, the solution is mechanical.

Inside the inventor's headCopy Anchor Link

Start with the problem that feels almost too small to be a DP: climbing stairs. You can climb 1 or 2 steps at a time; how many distinct ways are there to reach step n?

The naive instinct is to enumerate every sequence of 1s and 2s — and that explodes exponentially. The pivot is to stop thinking about whole paths and start asking a smaller, sharper question: what does it take to get to step n? You arrived there from step n−1 (one step up) or step n−2 (two steps up). Those are the only two ways in. So:

ways(n) = ways(n − 1) + ways(n − 2)

…which is Fibonacci in a stair costume. The whole trick is choosing the right state — "the number of ways to reach step i" — at which point the recurrence falls out.

Here's the trap most people step into, and it's worth naming: they pick a fuzzy state like "the ways to get up the stairs." A state has to be something you can index and combine. "Ways to reach exactly step i" is indexable and it combines; "ways to get up the stairs" is neither. A good state is a precise noun with an index on it.

For a max problem, the same discipline applies. House robber: houses in a row, each with money; you can rob any subset, but no two robbed houses may be adjacent. The state: "the most money you can get using only the first i houses." The recurrence:

Every 1D DP is this picture: at each step, a small set of choices, each reading back a fixed number of earlier states, combined with max, min, or +.

The final approachCopy Anchor Link

The recipeCopy Anchor Link

Three lines carry the whole solution. Everything else — which direction to iterate, whether you can shrink the space — is a consequence of those three.

The invariantCopy Anchor Link

For all these problems the invariant is identical and simple: after the loop, dp[k] holds the exact optimal answer for the subproblem defined on 0 … k. Bottom-up you get it by induction: base cases are correct, and each cell is computed from cells already proven correct. The one rule you must never break: never read a cell you haven't written yet — which is why the iteration order must follow the dependency order.

A worked traceCopy Anchor Link

Rob the row [2, 7, 9, 3, 1]. State dp[i] = best using houses 0 … i, recurrence dp[i] = max(dp[i−1], dp[i−2] + money[i]), base dp[0] = 2, dp[1] = max(2, 7) = 7.

Reading it as a graph, each state points back at the one or two states it depends on — the DP state graph, which is always a DAG you can walk in index order:

The answer is dp[4] = 12. Follow it back: dp[4] = dp[2] + 1 = 11 + 1, and dp[2] = dp[0] + 9 = 2 + 9 — so we rob houses 0, 2, and 4 for 2 + 9 + 1 = 12. Notice dp[i] only ever reads dp[i−1] and dp[i−2] — the last two cells and nothing else. That observation is the entire space optimization below.

The full implementationCopy Anchor Link

// O(n) space: keep the whole table. dp[i] = best using houses 0..ifunction robTable(h) {  if (h.length === 0) return 0;  if (h.length === 1) return h[0];  const dp = [h[0], Math.max(h[0], h[1])];  for (let i = 2; i < h.length; i++) {    dp[i] = Math.max(dp[i - 1], dp[i - 2] + h[i]);  }  return dp[h.length - 1];}// O(1) space: we only ever read the last two cells -- so keep two variablesfunction robRolling(h) {  let prev = 0, cur = 0;                 // dp[i-2], dp[i-1]  for (const money of h) {    const take = prev + money;           // rob it, skip the previous    const skip = cur;                    // skip it    prev = cur;    cur = Math.max(take, skip);  }  return cur;}

ComplexityCopy Anchor Link

The space column is the lesson: you can roll states into variables exactly when each cell reads a fixed number of immediate predecessors. Climbing stairs and house robber read two cells back, so they shrink to O(1). Coin change reads every earlier cell that corresponds to a coin, so its whole table has to stay live — no rolling possible.

Where you meet it todayCopy Anchor Link

• Making change / vending machines. "Fewest coins for this amount" is coin change, and it is literally running in cash-handling and ATM firmware.
• Financial series. "Best profit from one buy and one sell" and "best streak of gains" are Kadane-shaped 1D DPs, one running variable over a price array.
• Compression & streaming. Optimal prefix decisions (e.g. text justification, optimal line breaking) are 1D DPs over positions in the input.
• Scheduling with a rolling horizon. Choosing whether to take or skip each slot in a stream — the exact take vs skip shape of house robber — shows up in ad slotting and bandwidth allocation.

// dp[i] = fewest coins to make amount i. Base dp[0] = 0.function coinChange(coins, amount) {  const dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0;  for (let i = 1; i <= amount; i++)    for (const c of coins)      if (c <= i && dp[i - c] + 1 < dp[i]) dp[i] = dp[i - c] + 1;  return dp[amount] === Infinity ? -1 : dp[amount];}

RecapCopy Anchor Link

• Every 1D DP is three lines: define the state, write the recurrence, set the base cases.
• A good state is a precise, indexable noun: "the best using the first i items," not "the answer."
• Fill the table in dependency order and never read a cell you haven't written.
• Roll states into variables (O(n) → O(1)) exactly when each cell reads a fixed few immediate predecessors — two cells, two variables.
• The trio: climbing stairs (sum of two), house robber (max of two), coin change (min over many). Master those and the pattern generalizes.

Next up: 2D Dynamic Programming & Grids — when the state needs two indices, and the table becomes a grid.