1D Linear DP

A one-dimensional dynamic program answers "best result using the first $i$ items" for every $i$, building each answer from a fixed handful of earlier ones. The state is just the position, the transition is take or skip, and the fill is one left-to-right pass. House robber is the classic example, since taking nums[i] rules out its neighbor, making dp[i] the larger of dp[i-1] and dp[i-2] + nums[i].

Part	The question it answers	In house robber
State	What does the future need to know?	Best total over the first $i$ values
Transition	How does one more item change it?	Skip it, or take it and drop the neighbor
Fill order	Which answers must exist first?	Left to right, two values kept

The state has to be sufficient, not just small. When a rule needs more context, such as not skipping two elements in a row or wrapping around a circular array, widen the state or split into cases rather than trying to force a single recurrence. Once choices depend on a remaining budget or a second sequence rather than just adjacent positions, the table gains another dimension, which leads into the specialized DP categories in Tier 3.

Approach	Time	Extra space
Backtrack over take or skip	$O(2^n)$	$O(n)$
Memoized recursion	$O(n)$	$O(n)$ table plus the stack
Bottom-up with two variables	$O(n)$	$O(1)$

Use it when choices along a sequence only interact with a fixed number of immediate neighbors, and the question asks for the best total or the number of valid ways.

The problems below start with the classic non-adjacent take-or-skip recurrence, move to a variation where you cannot skip two elements in a row, and end with counting valid digit-string decodings where the transitions add instead of taking a max.