DPAlgorithmaka linear DP, prefix DP, sequence DP

1D (Linear) DP

State is a single index into a sequence; dp[i] is the best answer for the prefix (or suffix) ending at i.

▶ VisualizePattern: Dynamic ProgrammingPractice (6)
Progress

Overview

In 1D DP the state is one integer i, and dp[i] summarizes the best/count/feasibility for the first i elements (or for the prefix ending exactly at i, which is a subtly different and often more useful definition). Transitions look back a constant number of positions (dp[i-1], dp[i-2]) or all earlier positions (max over j < i), giving O(n) or O(n²) respectively.

This is the entry point to DP: Fibonacci Numbers, Climbing Stairs, House Robber, Kadane's Algorithm (max subarray), and Coin Change over the amount axis are all 1D. Longest Increasing Subsequence is 1D with an O(n) transition. Decode Ways, Jump Game, Word Break (index over the string) and "min cost climbing stairs" belong here too.

Typical constraints: n ≤ 10^5–10^6 for O(n) transitions, n ≤ 5000 for O(n²) "look at every earlier j" transitions.

linearprefixO(n)rolling variables

Intuition

A mental model before the formal terms.

Walk along the array from left to right carrying a small backpack of facts about what you have already passed. For house robber the backpack holds two numbers: the best loot if you robbed the previous house, and the best if you did not. Each new house updates those two numbers; you never look further back.

The two flavours of dp[i] matter: "best over the whole prefix" is monotone and the answer is dp[n]; "best ending exactly at i" is not monotone and the answer is max over i — Kadane's Algorithm and Longest Increasing Subsequence use the latter because the "ending here" condition is what makes the transition local.

How it works

  1. State: dp[i] = answer for elements 0..i-1 (prefix of length i), or for the segment ending at index i. Say which one aloud; it fixes the base case and the final answer.
  2. Transition: enumerate what happens to element i: taken or skipped (dp[i] = max(dp[i-1], dp[i-2] + a[i]) in house robber), extended or restarted (dp[i] = max(a[i], dp[i-1] + a[i]) in Kadane), or which earlier j it attaches to (dp[i] = 1 + max dp[j] for j < i, a[j] < a[i] in LIS).
  3. Base case: dp[0] for the empty prefix (0, 1 way, or true), and sometimes dp[1] explicitly.
  4. Order: increasing i. Table: array of n + 1. Optimization: if only dp[i-1..i-k] is read, keep k variables.

Why it works

Optimal substructure: the best solution for the prefix of length i either does not involve element i-1 (then it is the best for prefix i-1) or does, in which case removing that element leaves an optimal solution to a strictly shorter prefix. The transition enumerates these cases exhaustively.

Since i only decreases across a transition, evaluating in increasing i is a valid topological order.

Recognition

How to tell a problem wants this.

  • A single array or string is processed left to right and each decision affects a bounded window of neighbours ("no two adjacent", "steps of 1 or 2", "decode 1 or 2 digits").
  • Asks for the best contiguous or non-contiguous selection from a sequence, or the number of ways to segment/decode it.
  • A greedy left-to-right pass is tempting but a counterexample exists (e.g. [2, 7, 9, 3, 1] for house robber).
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related House Robber visualization.

2
0
7
1
9
2
3
3
1
4
8
5
4
6
0123456
27·····
1/12Base cases: with one house rob it (2); with two houses rob the richer one (7) because adjacent houses cannot both be robbed.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn House Robber →
1dp[0] = v[0]; dp[1] = max(v[0], v[1])
2for i in 2 .. n-1:
3  take = dp[i-2] + v[i]
4  skip = dp[i-1]
5  dp[i] = max(take, skip)
6return dp[n-1]
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1# house-robber: dp[i] = best loot from houses 0..i-1
2dp[0] = 0, dp[1] = a[0]
3for i in 2..n:
4  dp[i] = max(dp[i-1], dp[i-2] + a[i-1])   # skip house i-1, or rob it
5return dp[n]

Implementations

1# Representative problem: house robber (max sum of non-adjacent elements)
2def rob(houses: list[int]) -> int:
31 · Handle the empty case
4    n = len(houses)
5    if n == 0:
6        return 0
72 · Table and base cases
8    dp = [0] * (n + 1)          # dp[i] = best loot from the first i houses
9    dp[1] = houses[0]
103 · Transition: skip house i-1, or rob it
11    for i in range(2, n + 1):
12        dp[i] = max(dp[i - 1], dp[i - 2] + houses[i - 1])
134 · Read the answer
14    return dp[n]
15 
16 
175 · Space-optimized rolling variables
18def rob_o1(houses: list[int]) -> int:
19    prev2 = prev1 = 0           # dp[i-2], dp[i-1]
20    for h in houses:
21        prev2, prev1 = prev1, max(prev1, prev2 + h)
22    return prev1
23 
24 
25if __name__ == "__main__":
26    print(rob([2, 7, 9, 3, 1]), rob_o1([2, 7, 9, 3, 1]))  # 12 12
Walkthrough
  1. Representative 1D DP: dp[i] is the best loot from the first i houses.
  2. [0] * (n + 1) builds the table with the base dp[0] = 0; dp[1] = houses[0].
  3. The transition max(dp[i-1], dp[i-2] + houses[i-1]) is "skip" vs "rob" for house i-1.
  4. rob_o1 uses tuple assignment to slide the two trackers forward in one statement.
  5. Both print 12 for [2, 7, 9, 3, 1].
Complexity (this implementation)
time O(n) · space O(n), O(1) with rolling variables
Language notes
  • prev2 = prev1 = 0 chained assignment binds both names to the same immutable int — safe here, not safe with lists.
  • Built-in max on two ints is fine; for many candidates use a generator, not a temporary list.
  • Slices copy: rob_o1(houses[1:]) for House Robber II costs O(n) extra memory.
Common mistakes in this language
  • Returning dp[n - 1] instead of dp[n].
  • Using houses[i] instead of houses[i - 1] with the prefix-length convention.
  • Writing the rolling update as two statements in the wrong order.

Complexity

Best
—
Average
—
Worst
O(n) with O(1) transitions; O(n²) when each state scans all earlier states
Space
O(n), usually reducible to O(1)

LIS-style O(n²) transitions can sometimes be sped up with binary search or a segment tree.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • One sequence, decisions depend on a bounded window of previous positions.
  • Answer for a prefix is a function of answers for shorter prefixes.
  • The problem is a chain of "take / skip" or "extend / restart" choices.
Avoid it when
  • Two sequences interact (alignment, common subsequence) — that needs 2D (Two-Sequence) DP.
  • The decision at i depends on an unbounded summary of the past that a single index cannot capture (e.g. which items were taken) — add a dimension or use Bitmask DP.
  • Contiguous max sum with all-positive numbers or a simple greedy suffices — no DP needed.

Alternatives

Kadane's AlgorithmState Machine DPGreedy AlgorithmsPrefix Sum

Common mistakes

  • Confusing "best for prefix of length i" with "best ending at i" — the base cases and final answer differ.
  • Returning dp[n-1] when the table is sized n + 1 with a zero base, or vice versa.
  • Forgetting that "ending here" DPs need max over all i, not dp[n-1].
  • Initializing dp[0] to 0 in counting problems where the empty prefix has exactly one way.

Interview patterns

  • House Robber I/II (circular: run twice, excluding first or last).
  • Decode Ways, Climbing Stairs with variable steps, Min Cost Climbing Stairs.
  • Word Break with dp[i] = "prefix of length i is segmentable".
  • Jump Game (feasibility) and Jump Game II (min jumps, which is also solvable greedily).
Interview questions on this
Mock interviews

Example problems

Climbing StairseasyHouse RobbermediumWord BreakmediumLongest Increasing SubsequencemediumMaximum SubarraymediumJump Gamemedium