1D DP

1D DP problems have state indexed by a single number — typically a position in an array. The recurrence usually depends on only the last one or two states, so you can reduce space from $O(n)$ to $O(1)$.

Fibonacci

The "hello world" of DP. $F(n) = F(n - 1) + F(n - 2)$ with $F(0) = 0$, $F(1) = 1$. Naive recursion is $O(2^n)$ — exponential, because $F(n - 2)$ is computed many times. DP makes it $O(n)$ time, $O(1)$ space.

Climbing stairs

You can climb 1 or 2 stairs at a time. How many ways to climb $n$? Answer: $F(n + 1)$. Same recurrence: ways to reach step $i$ = ways to reach $i - 1$ (then take a 1-step) plus ways to reach $i - 2$ (then take a 2-step).

House robber

Houses in a row; you can't rob two adjacent. Maximize loot. Recurrence: $f(i) = \max(f(i - 1), f(i - 2) + A[i])$ — either skip the current house or take it and add the best up to $i - 2$.

Longest increasing subsequence

$f(i)$ = length of LIS ending at index $i$. Then $f(i) = 1 + \max_{j < i, A[j] < A[i]} f(j)$, with $f(i) = 1$ if no such $j$. Final answer: $\max_i f(i)$. $O(n^2)$ — and a clever patience-sorting variant gets it to $O(n \log n)$.

Coin change (minimum coins)

Minimum coins to make change for $n$ from denominations $\{c_1, c_2, \dots\}$. $f(n) = 1 + \min_i f(n - c_i)$, with $f(0) = 0$ and unreachable amounts marked $\infty$. $O(n \cdot |C|)$.

Pattern

When you see "ways to do X" or "best/min/max over a sequence" with the constraint that each choice depends on the last 1-2 choices, you're looking at a 1D DP. The recurrence almost always involves max/min/+ over a tiny set of predecessors.