DP — 1D

TL;DR

One-dimensional DP is the simplest non-trivial DP shape: the state is a single index i, and dp[i] is the answer to the subproblem ending at (or using up to) position i. The transition expresses dp[i] as a function of a small, fixed number of earlier states — usually dp[i-1], dp[i-2], or a window of dp[i-k] for k ranging over a set of choices.

The mental ladder for every 1D DP problem is the same: write the recursion first (top-down, ignoring efficiency), bolt on memoisation (cache results by i), then flip it into tabulation (bottom-up loop filling dp[] left to right), and finally space-optimise if only the last k states are ever read. Skipping straight to tabulation is how off-by-ones happen — the recursion is where the base cases and transition become obvious.

If a problem says “ways to climb / pick / decode”, “minimum cost to reach position n”, or “maximum total over choices made up to index i”, the state is almost certainly a single integer, and you’re in 1D-DP territory.

When to reach for it

Signals that 1D DP is the right shape:

• Overlapping subproblems indexed by one number. A naive recursion recomputes the same f(i) exponentially many times — that’s the entire reason DP exists.
• Optimal substructure on prefixes. The best answer for 0..i can be built from the best answers for 0..j with j < i. If the answer at i needs the full configuration of earlier choices (not just summary values), 1D won’t be enough — you need 2D or bitmask DP.
• The problem narrates choices. “At each step you can do A or B” — climb one stair or two, rob this house or skip it, take this coin or not. The transition writes itself: dp[i] = combine(dp after choice A, dp after choice B).
• “Ways to” or “min/max over a sequence of decisions” are the two tells. Counting problems become sums, optimisation problems become min/max.

If the answer depends on two coordinates that move independently (two strings, a grid, a range [i, j]), this isn’t 1D — see the 2D-DP and interval-DP guides.

Flavor 1 — Fibonacci-shape: climbing stairs and house robber

The canonical 1D shape: dp[i] depends on the last one or two states. Climbing Stairs (LC 70) is literal Fibonacci: dp[i] = dp[i-1] + dp[i-2]. House Robber (LC 198) is the same skeleton with a max and a value:

# dp[i] = max loot from houses 0..i
# choice at house i: rob it (nums[i] + dp[i-2]) or skip it (dp[i-1])
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

The ladder, top to bottom. Recursion first:

def rob(nums):
    def f(i):
        if i < 0: return 0
        return max(f(i - 1), f(i - 2) + nums[i])
    return f(len(nums) - 1)

This is O(2^n) — every call branches twice. Memoise by i:

def rob(nums):
    memo = {}
    def f(i):
        if i < 0: return 0
        if i in memo: return memo[i]
        memo[i] = max(f(i - 1), f(i - 2) + nums[i])
        return memo[i]
    return f(len(nums) - 1)

Now O(n) time, O(n) stack + memo. Flip to tabulation:

def rob(nums):
    n = len(nums)
    if n == 0: return 0
    if n == 1: return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]

Only dp[i-1] and dp[i-2] are ever read, so you can collapse the array to two scalars:

def rob(nums):
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

O(n) time, O(1) space. Same algorithm, four representations.

Worked trace. nums = [2, 7, 9, 3, 1].

Answer: dp[4] = 12 — rob houses 0, 2, 4 for 2 + 9 + 1 = 12. The transition quietly enforces “no two adjacent”: picking house i forces you to inherit dp[i-2], which already excluded house i-1.

Flavor 2 — Coin Change (LC 322)

Given coin denominations and a target amount, find the fewest coins that sum to amount. State: dp[a] = minimum coins to make value a. Transition: try every coin and take the best.

dp[a] = min(dp[a - c] + 1  for c in coins  if a - c >= 0)

def coinChange(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Base case dp[0] = 0 matters: zero coins make value zero. Use a sentinel larger than any real answer (amount + 1) so unreachable states don’t accidentally win a min.

Worked trace. coins = [1, 2, 5], amount = 11.

dp[11] = 3 — built by 5 + 5 + 1. Notice that the table fills strictly left to right and every cell only reads cells to its left, which is what makes the order legal.

Flavor 3 — Longest Increasing Subsequence (LC 300)

Given an array, find the length of the longest strictly increasing subsequence (not contiguous — picks).

O(n²) DP. dp[i] = LIS length ending exactly at index i. To extend, scan all j < i where nums[j] < nums[i] and take the best:

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

For nums = [10, 9, 2, 5, 3, 7, 101, 18]:

Answer: max(dp) = 4.

O(n log n) — patience-sort trick. Maintain tails, where tails[k] is the smallest possible tail of any increasing subsequence of length k+1 seen so far. For each x, binary-search the leftmost tails[k] >= x and overwrite it (or append if x exceeds every tail). The length of tails at the end is the LIS length.

from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

tails is not the LIS itself — it’s a compressed summary. Reconstructing the actual subsequence needs predecessor pointers. For LIS-length-only, this is the version to ship.

Why it works — the invariant

At every point in the loop, dp[i] is the exact, final answer to “best/count considering positions 0..i”. The transition only reads dp[j] for j < i, which are already finalised — that’s why filling left-to-right is sound. Two things have to hold:

1. Optimal substructure. The optimum at i is built from optima at smaller indices, not from arbitrary suboptimal configurations.
2. Acyclic dependency. dp[i] reads only earlier indices. If the dependency went both ways, you’d need iteration to convergence (or a different state definition).

If you can’t write down a one-sentence definition of dp[i] without saying “and also” three times, the state is wrong. Redefine before coding.

Complexity

• Fibonacci-shape (climbing stairs, house robber, decode ways): O(n) time, O(1) space after the rolling-variable optimisation.
• Coin change: O(n × amount) time, O(amount) space, where n is the number of coin denominations.
• LIS: O(n²) for the DP version, O(n log n) for the patience-sort version. Both use O(n) space.
• Word break (LC 139): O(n² × L) where L is max word length, because for each position you check every dictionary word that could end there.

Common pitfalls

• Off-by-one in dp size. Decide once whether dp has length n (dp[i] is “answer at position i”) or n + 1 (dp[i] is “answer using first i elements”). The former returns dp[n-1], the latter returns dp[n]. Mixing them is the most common 1D-DP bug.
• Wrong base case. dp[0] = 1 for “ways to make value 0” (one way: the empty selection); dp[0] = 0 for “minimum coins to make value 0” (zero coins). Get this backwards and the whole table is shifted.
• Space-optimising too early. Get tabulation correct and tested first, then collapse to rolling variables. Trying to write the O(1)-space version from scratch hides the indexing structure and you’ll burn an hour finding the bug.
• Missing the include-vs-skip distinction. In House Robber, dp[i-2] + nums[i] is the include branch and dp[i-1] is the skip branch. Writing dp[i-1] + nums[i] instead of dp[i-2] + nums[i] would let you rob adjacent houses — silently wrong, no exception thrown.
• Using float('inf') for unreachable states without checking. Returning dp[amount] when it’s still inf gives a nonsense answer. Either use a finite sentinel (amount + 1) or branch on reachability before returning.

Where you see this in production

1D DP is everywhere once you know to look:

• UNIX diff and git diff. The line-level diff is longest common subsequence — a 2D DP, but the Hunt–Szymanski and Myers variants used in practice reduce most cases to a 1D rolling array over the edit graph.
• Spell checkers and fuzzy search. Levenshtein distance powers “did you mean” in search engines, IDE autocomplete, and git’s “did you mean commit?” suggestion. The classic implementation is 2D DP, but production spell checkers (Hunspell, Aspell) roll the table down to two rows — 1D in practice.
• Bioinformatics — BLAST and Smith–Waterman. Local sequence alignment for DNA/protein search is a banded 1D-DP sweep over each diagonal of the alignment matrix; the heuristic seed-and-extend phase that makes BLAST fast is itself a 1D DP over high-scoring segment pairs.
• PostgreSQL query planner. The dynamic-programming join-order optimiser (geqo is the genetic fallback; the default is straight DP) builds up the cheapest plan for joining k relations from the cheapest plans for joining k-1, indexed by a bitmask — the bitmask version of the same 1D ladder.
• GPU compiler instruction scheduling. List schedulers in LLVM and NVCC use 1D DP over instruction issue slots to pick the lowest-latency ordering, where dp[i] is the best schedule using cycles 0..i.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• Striver / Take U Forward — DP playlist — www.youtube.com — Builds the recursion → memo → tabulation ladder.