Dynamic Programming: 1D
On this page
Dynamic programming is recursion that remembers. If the brute-force recursion solves the same smaller problem many times, store each answer the first time and reuse it. In one-dimensional DP, a smaller problem is described by one number: a prefix of the array, an amount of money, a position in a string. You fill a list dp where dp[i] is the answer for that smaller problem.
The code is always short. The work is in four decisions, made in this order:
- State: what does
dp[i]mean, in one sentence? - Recurrence: how does
dp[i]come from smaller states? - Base case: which states are known without thinking?
- Order: fill states so everything
dp[i]needs is ready first.
When to recognise it
- "Minimum / maximum / number of ways" to reach something: fewest coins, most money robbed, ways to climb stairs, ways to decode.
- "Can it be done?" where a choice at each step affects later steps: word break, jump game variants.
- A brute force that branches ("take it or skip it", "use this coin or not") and repeats work.
- Longest increasing / alternating subsequence: the state is "best ending at index i".
- Contrast with Greedy: if one local rule always works, you don't need DP. If you can build a counterexample to the greedy rule (coins
[1, 3, 4], amount 6), you need DP.
Example: house robber
You can't rob two neighbouring houses. State: dp[i] = the most money from the first i houses. Recurrence: for house i, either skip it (dp[i − 1]) or rob it and skip its neighbour (dp[i − 2] + houses[i − 1]).
![Houses [2, 7, 9, 3, 1] above a dp row [0, 2, 7, 11, 11, 12]. dp[1] and dp[2] are highlighted as inputs to dp[3]: max(7, 2 + 9) = 11.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-dd3e4853.png)
Since dp[i] reads only the two states before it, two variables replace the list:
def rob(houses):
"""dp[i] = best using houses[:i]. Only the last two states matter, so keep two variables."""
prev2 = prev1 = 0 # dp[i-2], dp[i-1]
for x in houses:
prev2, prev1 = prev1, max(prev1, prev2 + x) # skip house i, or take it
return prev1
Time O(n), space O(1).
Template: bottom-up table
def coin_change(coins, amount):
"""Bottom-up: dp[a] = fewest coins to make a. Fill small amounts first."""
INF = float('inf')
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[amount] if dp[amount] != INF else -1
![Coin change with coins [1, 2, 5]: a row of dp values for amounts 0 to 11 (0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3). dp[11] = 1 + min(dp[10], dp[9], dp[6]) = 3.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/001-7468999e.png)
Time O(amount × coins), space O(amount).
Top-down is the same thing
If the recurrence is clearer as recursion, write it that way and add a cache. In an interview this is a good first version; convert to a table if asked about recursion depth or speed.
from functools import lru_cache
def coin_change_memo(coins, amount):
"""Top-down: same recurrence written as recursion + cache. Good first draft in an interview."""
@lru_cache(maxsize=None)
def best(a):
if a == 0:
return 0
if a < 0:
return float('inf')
return 1 + min(best(a - c) for c in coins)
r = best(amount)
return -1 if r == float('inf') else r
Two more shapes
Look back over every split. dp[i] is true if some earlier dp[j] is true and the piece s[j:i] is a word:
def word_break(s, words):
"""dp[i] = can s[:i] be split? Look back at every possible last word."""
words = set(words)
dp = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
dp[i] = any(dp[j] and s[j:i] in words for j in range(i))
return dp[len(s)]
Best ending here. For the longest increasing subsequence, the O(n²) DP is dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). The faster version keeps, for each length, the smallest possible last value, and uses binary search:
import bisect
def lis_length(nums):
"""O(n log n): tails[k] = smallest tail of an increasing run of length k + 1."""
tails = []
for x in nums:
i = bisect.bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
Common bugs
- A fuzzy state. If you can't say what
dp[i]means in one sentence, the recurrence will be wrong. Write the sentence down. - Off-by-one between
dpand the input: withdp[i]meaning "first i items", itemiishouses[i − 1]. - Wrong base case:
dp[0] = 0for "fewest coins for amount 0", but1for "number of ways to make 0". - Unreachable states: start them at infinity (or −1) and check before using them, as
coin_changedoes. - Counting order matters. For "number of combinations" (coin change II), loop over coins outside and amounts inside; swapping the loops counts permutations instead.
Say this in the interview
- "Let dp[i] be the best I can do with the first i houses. For house i I either skip it, giving dp[i − 1], or take it, giving dp[i − 2] plus its value."
- "Each state is computed once from a constant number of earlier states, so it's O(n) time, and since I only look back two steps I can keep two variables."
Problems for this pattern
- Climbing Stairs:
dp[i] = dp[i − 1] + dp[i − 2]. - Maximum Subarray: best sum ending here.
- House Robber: skip or take.
- Coin Change: the table template.
- Decode Ways: one-digit and two-digit steps.
- Word Break: look back over every split.
- Longest Increasing Subsequence: best ending here, then the binary-search speed-up.
- Maximum Product Subarray: track both the max and the min ending here.
Related
DP 2D · Backtracking (the recursion before the cache) · Greedy · Binary Search