One sequence: dp[i] is the best subsequence ending at i, considering compatible j<i. Two sequences: dp[i][j] describes prefixes A[:i],B[:j]; matching ends pair, while mismatch skips a side or applies an edit.
Recognition signals
Elements may be deleted or skipped but relative order remains.
The objective is an increasing, common, edited, or matched sequence.
The last selected position cleanly separates a subproblem.
Two prefix indices are sufficient to describe the future.
Different selection histories converge on the same endpoint or prefix pair.
False friends
Signal
Why it is different
A contiguous subarray or substring
Contiguity favors a window, prefix aggregate, or local DP and does not permit arbitrary skips.
One subsequence-containment check
A single query is handled by two pointers in linear time.
Unordered set matching
If relative order is irrelevant, hashing, frequency counts, or graph matching may fit better.
Core invariant
Every computed state exactly matches its endpoint/prefix definition and includes all legal final match, skip, or edit actions.
State, transition, and processing order
Item
Definition
State
One ending index i or two prefix lengths (i,j), optionally with parent/action data for reconstruction.
Transition
Reason from the final action: pair equal ends, skip A's end, skip B's end, or perform replacement/insertion/deletion and aggregate.
Frontier / order
Increase i and j in dependency-DAG order. Two-dimensional rows can roll, though witness reconstruction usually needs more information.
Python skeleton
def lcs_length(a, b):
prev = [0] * (len(b) + 1)
for x in a:
cur = [0]
for j, y in enumerate(b, 1):
if x == y:
cur.append(prev[j - 1] + 1)
else:
cur.append(max(prev[j], cur[-1]))
prev = cur
return prev[-1]
Correctness sketch
The common subsequence length with an empty prefix is zero.
If final symbols match, an optimum may pair them and extend the shorter prefixes; if they differ, every optimum skips at least one final symbol.
The recurrence covers these final actions, and induction on prefix lengths proves the answer.
Complexity
Time
Space
Parameters
Typically O(mn) for two sequences and O(n²) for a naive one-sequence form
O(min(m,n)) for length with rolling rows; often O(mn) for reconstruction
m and n are sequence lengths.
Edge cases
empty sequences
duplicate symbols
equality or case-folding rules
length versus actual witness
rolling-row direction
nonuniform edit costs
Error patterns
Pattern
Why it fails / fix
Confusing subsequence with substring
A subsequence permits gaps; the state and recurrence must reflect skips.
Assuming a match always removes all alternatives
That safety depends on the objective; generalized costs may still require comparing other actions.
Aliasing rolling rows
prev and cur must be distinct layers, or current-row updates contaminate prior-prefix states.
Storing only length when a witness is required
Keep parents/full table or use a separate divide-and-conquer reconstruction.
Selection and exclusion rules
First distinguish contiguous from skippable.
Define an ending-index or prefix-pair state in one sentence.
List every possible final action.
Compress only when a length suffices; preserve reconstruction data for a witness.