DPAlgorithmaka two-string DP, alignment DP, prefix-pair DP

2D (Two-Sequence) DP

State is a pair of prefix lengths (i, j) over two sequences; dp[i][j] combines answers for shorter prefixes of each.

▶ Visualize Pattern: Dynamic Programming Practice (3)

Progress

Overview

When two sequences must be compared, aligned or merged, the natural state is dp[i][j] = answer for the first i characters of A and the first j of B. Transitions look at dp[i-1][j], dp[i][j-1] and dp[i-1][j-1] — "drop a char from A", "drop a char from B", "match/replace both". This is the shape of Longest Common Subsequence, Edit Distance, regular-expression and wildcard matching, interleaving strings, and distinct subsequences.

It is O(n·m) time and space; the space drops to O(min(n, m)) by keeping two rows (or one row with a saved diagonal). Typical constraints: n, m ≤ 1000–5000.

A second 2D family uses (i, k) with k a count rather than a second sequence: "at most k transactions", "exactly k groups", "using i items with j capacity" (Knapsack DP). The mechanics are the same; only the meaning of the second axis changes.

two sequencesO(nm)alignmentstringsrolling row

Intuition

A mental model before the formal terms.

Lay A along the top of a grid and B down the side. Each cell (i, j) is "how well do these two prefixes fit together?". Moving right consumes a character of A, moving down consumes one of B, moving diagonally consumes one of each. Any path from the top-left corner to the bottom-right corner is an alignment; the DP finds the best path by scoring each cell from its three neighbours.

For LCS, a diagonal step scores 1 when the two characters match; the table value is the longest chain of matching diagonals you can string together while only moving right/down.

How it works

State: dp[i][j] for prefixes A[0..i) and B[0..j). Size (n+1) × (m+1) to include empty prefixes.
Transition: if A[i-1] == B[j-1] there is a diagonal option; otherwise combine dp[i-1][j] and dp[i][j-1] (LCS: max; edit distance: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])).
Base cases: row 0 and column 0 — dp[0][j] = 0 for LCS, dp[0][j] = j for edit distance (j insertions), dp[0][0] = true for interleaving.
Order: row by row, left to right (all three dependencies are above or to the left). Table: 2D array. Optimization: two rows, or one row plus a diag temp holding the old dp[i-1][j-1].

Why it works

Any optimal alignment of A[0..i) and B[0..j) ends with one of exactly three events — the last char of A is unmatched, the last char of B is unmatched, or they are paired — and what remains is an optimal alignment of shorter prefixes. Enumerating the three and recursing is exhaustive and optimal.

Row-major order visits (i-1, j), (i, j-1) and (i-1, j-1) before (i, j), so the loop is a topological order of the dependency DAG.

Recognition

How to tell a problem wants this.

Two strings or arrays, and the question is about a common subsequence, a minimum edit, a pattern match, or whether one interleaves/contains the other.
Constraints |A|, |B| ≤ 1000–5000 — O(nm) is intended.
One sequence plus a count: "at most k operations", "split into k parts" — a 2D table over (index, count).

“number of ways” → Dynamic Programming

Interactive visualization

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

Showing the closely related Longest Common Subsequence visualization.

String X | string Y — Two strings separated by a pipe — e.g. "ABCBDAB | BDCABA". Up to 10 characters each

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·

1/44Row 0 and column 0 represent an empty prefix, whose LCS with anything is 0.

Cell being filledDependency readBase caseComputedReconstructed choice

PseudocodeLearn Longest Common Subsequence →

1dp[0][*] = dp[*][0] = 0
2for i in 1 .. m: for j in 1 .. n:
3  if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1
4  else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
5traceback from dp[m][n]

Variables

Complexity

best O(n·m)

avg O(n·m)

worst O(n·m)

space O(min(n, m))

Speed

Pseudocode

1# lcs: dp[i][j] = LCS length of A[0..i) and B[0..j)
2dp = (n+1) x (m+1) zeros
3for i in 1..n:
4  for j in 1..m:
5    if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1
6    else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
7return dp[n][m]

Implementations

1# Representative problem: longest common subsequence (LCS) of two strings
2def lcs(a: str, b: str) -> int:
3    n, m = len(a), len(b)
41 · Table over prefix pairs
5    dp = [[0] * (m + 1) for _ in range(n + 1)]   # dp[i][j]: a[:i], b[:j]
62 · Fill row by row
7    for i in range(1, n + 1):
8        for j in range(1, m + 1):
93 · Transition: match diagonally or drop one character
10            if a[i - 1] == b[j - 1]:
11                dp[i][j] = dp[i - 1][j - 1] + 1
12            else:
13                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
144 · Read the answer
15    return dp[n][m]
16 
17 
18if __name__ == "__main__":
19    print(lcs("abcde", "ace"))  # 3 ("ace")

Walkthrough

Representative example of 2D (two-sequence) DP: dp[i][j] is the LCS length of a[:i] and b[:j].
The comprehension [[0] * (m + 1) for _ in range(n + 1)] creates a distinct row per iteration — the safe way to build a 2D list.
Row 0 and column 0 hold the empty-prefix base cases and are never rewritten.
Each cell reads its up, left and diagonal neighbours, all already final under row-major order.
dp[n][m] is the LCS of the full strings.

Complexity (this implementation)

time O(n·m) · space O(n·m), reducible to O(min(n, m)) with two rows

Language notes

[[0] * (m + 1)] * (n + 1) is the classic trap: it aliases one row list n + 1 times.
CPython overhead makes the pure-Python O(n·m) loop slow for n, m ~ 5000; two-row rolling plus local-variable caching of dp rows helps constant factors.
For alignment reconstruction keep the full table and walk back from (n, m) following which arm won.

Common mistakes in this language

Building the table with list multiplication and corrupting every row on the first write.
Comparing a[i] with b[j] instead of a[i - 1] / b[j - 1].
Using recursion without a memo for LCS — exponential for even modest strings.

Language differences that matter here

Building a 2D table safely: Python needs a comprehension (list multiplication aliases rows), JS/TS need a per-row factory in Array.from (fill(row) aliases), C++ nested vectors copy by value and are safe.
Flat 1D storage (i * (m + 1) + j) is the standard performance upgrade in C++ and JS/TS (Int32Array); in Python the constant factor is dominated by the interpreter either way.
String indexing yields a char in C++ (char, comparable with ==) but a length-1 string in JS/TS/Python.

Complexity

Best

—

Average

—

Worst

O(n·m)

Space

O(n·m), reducible to O(min(n, m))

Reconstructing the alignment itself needs the full table (or Hirschberg's divide-and-conquer trick for linear space).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Comparing or aligning two sequences character by character.
One sequence with a bounded "budget" or count as the second dimension.
Sizes up to a few thousand each.

Avoid it when

Both sequences are ~10^5 — O(nm) is 10^10; look for structure (LIS-style patience sorting, suffix structures, hashing).
Only one sequence with a local transition — that is 1D (Linear) DP and a 2D table wastes memory.
Exact substring (not subsequence) matching — use Knuth–Morris–Pratt (KMP) or Rabin–Karp in linear time.

Alternatives

1D (Linear) DP Grid DP Knuth–Morris–Pratt (KMP)Subsequence DP

Common mistakes

Indexing A[i] instead of A[i-1] when dp[i] represents the prefix of length i.
Wrong base row/column — edit distance needs dp[i][0] = i and dp[0][j] = j, not zeros.
When rolling to one row, overwriting dp[i-1][j-1] before it is read; save it in a diag variable.
Iterating j in the outer loop while reading dp[i][j-1] in a way that is fine — but then trying to roll rows along the wrong axis.

Interview patterns

LCS, Edit Distance, Longest Common Substring (reset to 0 on mismatch), Shortest Common Supersequence.
Regular Expression / Wildcard Matching with * transitions referencing dp[i][j-2] or dp[i-1][j].
Distinct Subsequences (count), Interleaving String (boolean).
Best Time to Buy and Sell Stock IV as (day, transactions).

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced
Recognizing a dynamic-programming problemAdvanced

Mock interviews

Coin ChangeIntermediate

Example problems

Longest Common Subsequencemedium Edit Distancemedium Longest Palindromic Substringmedium

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·