DPAlgorithmaka LIS-style DP, ending-at DP, chain DP

Subsequence DP

State is "best subsequence ending at index i"; transition scans all earlier j that can precede i.

▶ VisualizePattern: Binary SearchPractice (2)
Progress

Overview

Subsequence DP handles problems about choosing elements in order but not necessarily contiguously, where the validity of adding element i depends only on the previous chosen element j. The state is dp[i] = best subsequence that ends exactly at i; the transition is dp[i] = best over j < i with compatible(j, i) of dp[j] + gain(i); the answer is the best dp[i] overall. Longest Increasing Subsequence is the canonical example (compatible = a[j] < a[i]).

The generic form is O(n²), suitable for n ≤ 5000. When compatible is an ordering (<, ≤) and gain is uniform, the patience-sorting / binary-search technique gives O(n log n) for Longest Increasing Subsequence; a Fenwick Tree or Segment Tree indexed by value gives O(n log n) for weighted variants (max-sum increasing subsequence).

Members: LIS and its count, longest divisible subset, longest chain of pairs, Russian doll envelopes (sort by width, LIS on height), longest arithmetic subsequence (dp[i][diff]), maximum sum increasing subsequence, and number of LIS.

subsequenceLISO(n²)ending at ipatience sorting

Intuition

A mental model before the formal terms.

Each element asks "which earlier element would I most like to follow?" and inherits that element's chain plus one. For [10, 9, 2, 5, 3, 7, 101, 18], 7 can follow 2, 5 or 3 (all smaller); the best of those chains has length 2, so dp[7] = 3. The answer is the longest chain anyone managed to build, not the last one.

Contrast with 1D (Linear) DP prefix DPs: here dp[i] is deliberately about subsequences that must include i, because "the previous chosen element is j" is the only history that matters and pinning i makes that history explicit.

How it works

  1. State: dp[i] = optimal subsequence value ending at index i (and including it). Sometimes a second dimension carries the "previous difference" or "previous element index" for two-element constraints.
  2. Transition: dp[i] = gain(i) + max(0 or base, dp[j] for j < i if compatible(j, i)). For counting, sum instead of max, and track ties for "number of longest".
  3. Base case: dp[i] = gain(i) (a subsequence of just element i).
  4. Order: increasing i. Answer: max over i of dp[i]. Optimization: replace the inner scan with a data structure keyed by value (binary search on "tails", Fenwick tree for prefix max) when compatible is a threshold on a[j].

Why it works

Removing the last element of an optimal subsequence ending at i leaves an optimal subsequence ending at some compatible j — otherwise swapping in a better one would improve the original. The transition enumerates all j, so it is exact.

Compatibility depends only on (j, i), not on earlier elements, so dp[j] is a sufficient summary of the chain before j.

Recognition

How to tell a problem wants this.

  • The word subsequence together with a pairwise condition on consecutive chosen elements (increasing, divisible, differing by d, non-overlapping intervals).
  • n ≤ 5000 suggests O(n²); n ≤ 10^5 with a simple ordering suggests O(n log n) patience sorting.
  • A greedy "take it if it extends the current chain" fails on inputs like [1, 5, 2, 3, 4].
“sorted array” → Binary Search“number of ways” → Dynamic Programming

Interactive visualization

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

Showing the closely related Longest Increasing Subsequence visualization.

3
0
1
1
8
2
2
3
5
4
4
5
9
6
6
7
01234567
11111111
1/30dp[i] = length of the longest increasing subsequence ending exactly at i. Every element alone is a subsequence of length 1.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Longest Increasing Subsequence →
1dp[i] = 1 for all i   // LIS ending at i
2for i in 1 .. n-1:
3  for j in 0 .. i-1:
4    if a[j] < a[i] and dp[j] + 1 > dp[i]:
5      dp[i] = dp[j] + 1; prev[i] = j
6answer = max(dp); reconstruct via prev
Variables
n8
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed

Pseudocode

1# LIS, O(n^2): dp[i] = length of longest increasing subsequence ending at i
2dp = [1] * n
3for i in 0..n-1:
4  for j in 0..i-1:
5    if a[j] < a[i]: dp[i] = max(dp[i], dp[j] + 1)
6return max(dp)

Implementations

1from bisect import bisect_left
2 
3# Subsequence DP: the state is a position in each sequence, and the choice at
4# every step is "does this element participate". Representative example:
5# longest common subsequence, with reconstruction and the two-row variant.
6 
7 
81 · dp[i][j] = LCS length of a[0..i) and b[0..j)
9def lcs_table(a: str, b: str) -> list[list[int]]:
10    n, m = len(a), len(b)
11    dp = [[0] * (m + 1) for _ in range(n + 1)]
12    for i in range(1, n + 1):
13        ai = a[i - 1]
14        row, prev_row = dp[i], dp[i - 1]
15        for j in range(1, m + 1):
162 · Characters match: extend the diagonal. Otherwise drop one side.
17            row[j] = prev_row[j - 1] + 1 if ai == b[j - 1] else max(prev_row[j], row[j - 1])
18    return dp
19 
20 
213 · Reconstruction walks the table backwards, retracing the choices
22def lcs(a: str, b: str) -> str:
23    dp = lcs_table(a, b)
24    out: list[str] = []
25    i, j = len(a), len(b)
26    while i > 0 and j > 0:
27        if a[i - 1] == b[j - 1]:
28            out.append(a[i - 1])
29            i -= 1
30            j -= 1
31        elif dp[i - 1][j] >= dp[i][j - 1]:
32            i -= 1
33        else:
34            j -= 1
35    return "".join(reversed(out))
36 
37 
384 · Only the previous row is read, so two rows suffice for the length
39def lcs_length(a: str, b: str) -> int:
40    shorter, longer = (a, b) if len(a) <= len(b) else (b, a)
41    prev = [0] * (len(shorter) + 1)
42    cur = [0] * (len(shorter) + 1)
43    for lc in longer:
44        for j in range(1, len(shorter) + 1):
45            cur[j] = prev[j - 1] + 1 if lc == shorter[j - 1] else max(prev[j], cur[j - 1])
46        prev, cur = cur, prev
47    return prev[len(shorter)]
48 
49 
505 · A different subsequence shape: longest increasing subsequence in O(n log n)
51def lis(a: list[int]) -> int:
52    tails: list[int] = []  # tails[k] = smallest tail of a length-(k+1) increasing subsequence
53    for x in a:
54        i = bisect_left(tails, x)
55        if i == len(tails):
56            tails.append(x)
57        else:
58            tails[i] = x
59    return len(tails)
Walkthrough
  1. [[0] * (m + 1) for _ in range(n + 1)] builds distinct rows; [[0] * (m+1)] * (n+1) would alias one row.
  2. row, prev_row = dp[i], dp[i - 1] hoists both rows into locals before the inner loop, removing two list indexings per iteration — a significant win in CPython.
  3. ai = a[i - 1] similarly hoists the character out of the inner loop.
  4. prev, cur = cur, prev swaps the two list *references* in O(1).
  5. bisect_left(tails, x) is exactly the LIS binary search, C-implemented — this is one place where Python has the primitive and JavaScript does not.
Complexity (this implementation)
time O(n*m) for LCS; O(n log n) for LIS · space O(n*m) for the table, O(min(n, m)) for the length-only version

The nested loop is pure Python and is the slow part; difflib.SequenceMatcher is C-backed and solves a closely related problem much faster.

Language notes
  • bisect_left gives strictly-increasing LIS; bisect_right gives non-decreasing — a one-word switch between two different problems.
  • Hoisting dp[i] and dp[i-1] into locals is the standard CPython optimisation for a 2D DP and typically gives 2-3x.
  • "".join(reversed(out)) is the idiomatic reverse-and-join; reversed() returns an iterator that join consumes without an intermediate list.
  • difflib.SequenceMatcher computes matching blocks (a related but not identical notion) in C and is worth knowing before hand-rolling LCS.
Common mistakes in this language
  • Building the table with [[0] * m] * n and aliasing every row.
  • Using bisect_right when strictly increasing was meant, silently answering a different question.
  • Indexing dp[i][j] directly in the inner loop rather than hoisting the rows, which is several times slower for no reason.
Language differences that matter here
  • Binary search for LIS is a standard-library call in C++ (std::lower_bound) and Python (bisect_left), and must be written out in JS/TS — the same split as everywhere else.
  • Swapping the two DP rows is O(1) in all four, but the spelling differs: std::swap on vectors swaps pointers, while JS/TS destructuring and Python tuple assignment rebind references.
  • Row aliasing when building a 2D table is a live trap in Python ([[0]*m]*n) and JS/TS (fill with an array), and impossible in C++.
  • Hoisting the row into a local is a real optimisation in Python (attribute and index lookups are expensive) and largely irrelevant in C++, where the compiler does it.

Complexity

Best
—
Average
—
Worst
O(n²) generic; O(n log n) for LIS-type orderings via binary search or Fenwick tree
Space
O(n)

The O(n log n) tails array gives the length only; reconstructing the sequence needs parent pointers.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Choosing an ordered subset where only consecutive chosen elements constrain each other.
  • Longest/heaviest chain problems on arrays, pairs, or intervals after sorting.
  • Counting the number of optimal subsequences.
Avoid it when

Alternatives

Longest Increasing SubsequenceLongest Common SubsequenceKnapsack DPKadane's AlgorithmBinary Search

Common mistakes

  • Returning dp[n-1] instead of max(dp) — the longest chain rarely ends at the last element.
  • Initializing dp[i] = 0 instead of 1 (each element alone is a subsequence of length 1).
  • In the O(n log n) version, believing tails is the actual LIS — it is not; it is a set of minimal tails.
  • Using bisect_right (non-strict) when strictly increasing is required, or vice versa.
  • Forgetting to sort first in pair/envelope problems, and to sort the secondary key descending to prevent same-width chains.

Interview patterns

  • LIS, Number of LIS, Longest Arithmetic Subsequence, Longest Divisible Subset.
  • Russian Doll Envelopes, Maximum Length of Pair Chain (sort + LIS).
  • Maximum Sum Increasing Subsequence (weighted; Fenwick tree for speed).
  • Longest String Chain (sort by length; dp over words via hash map).
Interview questions on this
Mock interviews

Example problems

Longest Increasing SubsequencemediumLongest Common Subsequencemedium