1D dynamic programming

What it is

A 1D dynamic program tracks one running quantity per position in a sequence, where the value at position i is computed from the values at a small, fixed set of earlier positions — usually just i-1 and i-2. The whole technique is: figure out what the last "move" could have been (the last step taken, the last character consumed, whether the current element was included or skipped), express the answer at i in terms of the answers at those specific earlier positions, and fill left to right. Because only the last one or two values are ever read, almost every 1D DP collapses from an O(n) array to two or three rolling variables.

When it applies

• The problem asks to count or optimize over sequences built step by step, where a step's effect depends only on a constant amount of local history (how many ways to reach a total, the best score ending here, whether the previous item was taken).
• The recurrence has a natural "last move" decomposition: the last step was of size 1 or 2, the last character was consumed alone or paired with the one before it, the current element was picked or skipped.
• It does not apply once the state needs to remember something that grows with the input — a start-to-end interval, a full subset of previous choices, or an unbounded lookback — those need a 2D table, bitmask DP, or a different technique.
• A circular arrangement (first and last elements adjacent) breaks the straightforward left-to-right fill; that needs the linear DP run twice with different endpoints excluded, not a direct recurrence.

Tells in the problem

• "Count the number of distinct ways to..." with a fixed small set of step sizes — a Fibonacci-shaped recurrence, ways[i] = sum over each step size s of ways[i-s].
• "No two selected elements may be adjacent" — a take-or-skip recurrence, best[i] = max(best[i-1], best[i-2] + value[i]).
• "...arranged in a circle" layered on top of a no-adjacent constraint — solve the linear version twice, once excluding each endpoint, and take the better result.
• A running product or sum where a sign flip (a negative number) can turn the worst running value into the best one — track both a running maximum and a running minimum, not just one.
• "Split this sequence into valid groups/codes" where a group can be length 1 or 2 (or a small fixed set of lengths) — the count at position i sums contributions from each valid group ending there.

The classic mistake

Code that only carries forward the single most recent value quietly assumes the last move could only ever be of one size — for example, forgetting that a decode step can consume either one digit or two, or that a running product's best next value might come from extending the minimum seen so far rather than the maximum, because a negative number flips their roles. This produces code that passes the examples with only positive numbers or single-length moves and silently breaks the moment the input includes the case the extra state was there to handle. The second common mistake is getting a base case wrong in a way that doesn't cause a crash — an off-by-one in what "zero prior steps" or "empty prefix" should count as — which then propagates through every later value without ever throwing an error. Before coding, write out the last-move cases explicitly and check the base case against the smallest possible input by hand.

Questions to start with

• Climbing Stairs — the purest form of the last-move decomposition, with exactly two step sizes and a clean Fibonacci recurrence.
• House Robber — the take-or-skip recurrence, and the standard counterexample showing why a greedy "every other element" rule fails.
• Decode Ways — the same two-lookback shape as Climbing Stairs, but with validity conditions (leading zeros, code ranges) that make the base case worth deriving carefully.
• Maximum Product Subarray — the case where one rolling value isn't enough: a running minimum must be tracked alongside the maximum because a negative number swaps their roles.
• House Robber II — the circular variant, solved by running the linear DP twice with a different endpoint excluded each time.