CHAPTER 09 · Subsequence DP

Subsequence DP

A subsequence keeps the original order but does not have to be contiguous. That single condition decides how every state in this chapter is defined. One sequence gives you a one-dimensional table (LIS). Two sequences give you a two-dimensional table, where each cell answers a question about one pair of prefixes. LCS, edit distance, and the palindrome problems are that same table with a different rule in the mismatch case.

§01

First: subsequence (may skip) vs subarray (must be contiguous)

This one condition decides how the state is defined, and what happens to a cell when the two characters do not match.

Every problem in this chapter turns on two words. Fix them first.

A subsequence is what you get by taking some elements out of a sequence in their original order, with gaps allowed. In "abcde", "ace" is a subsequence.
A subarray (called a substring when the sequence is a string) is a contiguous block of the sequence. In "abcde", "bcd" is a substring; "ace" is not.

Why does this matter before any code is written? Because it decides the shape of the transition. A contiguous problem must reset a cell to 0 the moment the two current elements differ, since the run is broken (LC 718). A subsequence problem may skip the mismatching element and keep the best result found so far (LC 1143). Same two-dimensional table, one different rule. Try it below.

Subsequence or subarray: pick some characters and see which one you get

Pick a few characters. Whatever you pick is always a subsequence. It is a subarray only when the indexes you picked are next to each other.

green = also a subarray · amber = subsequence only

Subsequence · gaps allowed

State: "the first i", or "ending at i"

Because elements may be skipped, "do not use this element" is always a legal move. So a mismatch carries the better of the smaller states forward with max, and never resets. Examples: LIS, LCS, edit distance.

Subarray · must be contiguous

State: almost always "ending at i"

A run has a definite last element, and one mismatch destroys the whole run. So a mismatch resets the cell to 0, and the answer is the maximum over the whole table. Examples: LC 718, maximum subarray sum (LC 53).

The most common mistake here

Read the problem and ask one question first: does it need the order kept, or does it need the elements next to each other? "Longest common subsequence" and "longest common subarray" differ by one word, and their transitions are not the same (sections 03 and 04 put the pair side by side). Misreading the question means defining the wrong state, and everything after that is wasted work.

§02

Worked example A · longest increasing subsequence

MEDIUM

LC 300 — subsequence DP on a single sequence, then the same answer in O(n log n).

The problem: given an array, find the length of the longest strictly increasing subsequence. Gaps are allowed. For [1, 3, 2, 4, 5] the answer is 4, from [1, 3, 4, 5] or [1, 2, 4, 5].

Brute force: each element is either taken or not, so there are 2ⁿ subsequences to check. At n = 40 that is already out of reach. Why DP applies: the problem has optimal substructure — remove the last element of a long increasing subsequence and what remains is still an increasing subsequence. So the real question is how to define the state.

Here is the central technique of subsequence DP: anchor the subproblem by its last element. Define dp[i] as the length of the longest increasing subsequence that ends at index i. Why insist on "ends at i"? Because only a fixed last element lets you ask whether one subsequence can be extended by another: look left for every j with nums[j] < nums[i], take the largest dp[j], and add 1. The base case is dp[i] = 1, since the element alone is already a subsequence. Step through it:

LC 300 · dp[i] = longest increasing subsequence ending at i (nums = [1, 3, 2, 4, 5])

nums

State first: dp[i] is the length of the longest increasing subsequence that ends at index i. The words "ends at i" are what make this work: once the last element is fixed, you can ask whether one subsequence may be extended by another element. Every cell starts at 1, because the element on its own is already a subsequence of length 1.

1 / 7

lc300_lis_n2.py

1class Solution:

2 def lengthOfLIS(self, nums: list[int]) -> int:

3 n = len(nums)

4 dp = [1] * n # every element alone has length 1

5 for i in range(1, n):

6 for j in range(i):

7 if nums[j] < nums[i]: # nums[i] can follow nums[j]

8 dp[i] = max(dp[i], dp[j] + 1)

9 return max(dp) # the answer is the largest cell

max(dp) reads the answer in one line. It raises an error on an empty list, which is safe here because LC 300 guarantees n ≥ 1.

Time O(n²), space O(n). LC 300 can be solved faster with a greedy idea plus binary search, known as patience sorting. Keep an array tails in which tails[k] is the smallest possible last value among all increasing subsequences of length k+1 seen so far. For each new value, use binary search (the lower-bound template from Chapter 03) to find the first entry that is ≥ it and replace that entry. If every entry is smaller, append instead. tails stays sorted, and its length is the answer:

LC 300 · how tails grows (nums = [1, 3, 2, 4, 5])

Read 1. tails is empty, so there is nothing to replace: append it. tails = [1], and the longest length found so far is 1.

1 / 5

lc300_lis_nlogn.py

1import bisect

3class Solution:

4 def lengthOfLIS(self, nums: list[int]) -> int:

5 tails = []

6 for x in nums:

7 i = bisect.bisect_left(tails, x) # first index with tails[i] >= x

8 if i == len(tails):

9 tails.append(x) # larger than all: append

10 else:

11 tails[i] = x # else: smaller ending

12 return len(tails)

bisect_left does the binary search in one line. For the longest non-decreasing subsequence, where equal values are allowed, switch it to bisect_right.

tails holds a length, not a subsequence

The length of tails is the correct answer, but the values inside it are not a valid subsequence of the input in general. A later replacement can overwrite an entry with a value that appears earlier in the array than the entries to its left. For nums = [3, 4, 1], tails ends as [1, 4], yet 1 comes after 4 in the input. If you also need to reconstruct one actual longest subsequence, record the position each value was placed at and follow those links backwards, or use the O(n²) version, where the predecessor of every cell is available directly.

Complexity

O(n²) → O(n log n)

The inner loop that scans everything to the left is replaced by one binary search: n operations, O(log n) each. At n = 10⁵, O(n²) is about 10 billion steps and the binary-search version is under two million.

Variant · LC 673

Counting the longest ones

Keep cnt[i] next to dp[i]: when a longer subsequence is found, reset the count; when the same length is matched, add to it. A main array plus a counting array is the standard shape of a counting DP.

Easy to get wrong

⚠️ The answer is not in the last cell

dp[i] is about subsequences that end at i, and the longest one does not have to end at the last element. Take the maximum over the whole dp array.

The name "patience sorting" comes from a card game

The technique is named after the card game patience, called solitaire in the United States. Deal the cards one at a time and put each card on the leftmost pile whose top card is not smaller than it; if there is no such pile, start a new pile on the right. When the deck is finished, the number of piles equals the length of the longest increasing subsequence. The top cards of the piles, read from left to right, are exactly the tails array in the code above.

In practice: diff tools are built on subsequence DP

git diff and text comparison tools look for the longest sequence of lines that both files share in the same order. That is the longest common subsequence of the next section, with whole lines instead of characters. Real diff tools do not fill a plain m×n table. They use refinements such as the Myers algorithm, or Hunt–Szymanski, which turns the LCS problem into an LIS problem and is fast when the two files have few identical lines in common. The question they answer, though, is the one in the next section.

§03

The contiguous case: maximum length of repeated subarray

MEDIUM

LC 718 — the first two-dimensional table in this chapter, and the rule that a mismatch resets a cell.

The problem: given two integer arrays A and B, find the length of the longest contiguous block that appears in both. It asks for a subarray, so the elements must be next to each other, and that is what fixes the state.

Brute force: pick a start in A, pick a start in B, and compare forwards, which costs O(m·n·min(m, n)). The DP: the standard opening for a two-sequence problem is a two-dimensional table with A along the rows and B along the columns. Because the block has to be contiguous, the state must pin down where the block ends: dp[i][j] = the length of the longest common run ending exactly at A[i-1] and B[j-1]. Equal elements extend the run on the diagonal by one. Unequal elements break the run, so the cell goes back to 0:

LC 718 · filling the table cell by cell (blue dashed cell = the source; a mismatch resets to 0)

∅

A = [1, 2, 3, 2, 1] along the rows, B = [3, 2, 1, 4, 7] along the columns. State: dp[i][j] is the length of the longest common run that ends exactly at A[i-1] and at B[j-1]. "Ends exactly at" is the wording a contiguous problem needs, because a run has a definite last element.

1 / 27

lc718_max_repeated_subarray.py

1class Solution:

2 def findLength(self, a: list[int], b: list[int]) -> int:

3 m, n = len(a), len(b)

4 dp = [[0] * (n + 1) for _ in range(m + 1)]

5 ans = 0

6 for i in range(1, m + 1):

7 for j in range(1, n + 1):

8 if a[i - 1] == b[j - 1]:

9 dp[i][j] = dp[i - 1][j - 1] + 1

10 ans = max(ans, dp[i][j])

11 return ans

A cell is only written when the two elements are equal; everything else keeps its initial 0. The table can be reduced to a single row, but then the row must be updated from right to left, because dp[j] reads the previous row's dp[j-1] and a left-to-right pass would already have overwritten it.

The zeros carry the information

The most informative cells in this table are not the 1s, 2s and 3s. They are the zeros. Each 0 says "a run cannot end here". The diagonal line of 1 → 2 → 3 is one common run growing. In the next section the same pair of sequences is used with the contiguity requirement removed, and those zeros disappear. That is the difference between LC 718 and LCS, seen directly in the table.

§04

Worked example B · longest common subsequence

MEDIUM

LC 1143 — the central table of this chapter, and where the diagonal transition is explained in full.

The problem: given two strings, find the length of their longest common subsequence: shared, in the same order, gaps allowed. For "abcde" and "ace" the answer is 3, from "ace".

The DP: the same opening as LC 718 — a two-dimensional table with one string along the rows and the other along the columns. But because the result does not have to be contiguous, the state can be simpler: dp[i][j] = the length of the longest common subsequence of the first i characters of A and the first j characters of B. Nothing is said about where it ends. The transition only looks at the two last characters:

Equal → matching this pair is never worse than leaving it out, so use it and add one to the answer for the two shorter prefixes: dp[i][j] = dp[i-1][j-1] + 1. The diagonal is the only cell that means "both characters consumed as one matched pair".
Different → they cannot be a matched pair, so at least one of them is unusable here. Drop A's last character and you are left with dp[i-1][j]; drop B's and you are left with dp[i][j-1]. One of the two must be optimal, so keep the larger: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — never a reset.

Base case: row 0 and column 0 are 0, because an empty string shares nothing. Fill the table one cell at a time and watch the blue dashed source cells change between a match and a mismatch:

LC 1143 · filling the table cell by cell (a match uses the diagonal; a mismatch takes the larger of above and left)

∅

A = "abcde" along the rows, B = "ace" along the columns. State: dp[i][j] is the length of the longest common subsequence of the first i characters of A and the first j characters of B. Row 0 and column 0 stand for an empty string, which shares nothing with anything, so they are all 0.

1 / 17

lc1143_longest_common_subsequence.py

1class Solution:

2 def longestCommonSubsequence(self, s: str, t: str) -> int:

3 m, n = len(s), len(t)

4 dp = [[0] * (n + 1) for _ in range(m + 1)]

5 for i in range(1, m + 1):

6 for j in range(1, n + 1):

7 if s[i - 1] == t[j - 1]:

8 dp[i][j] = dp[i - 1][j - 1] + 1

9 else:

10 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

11 return dp[m][n]

Off-by-one indexing is the most common bug in two-sequence DP. The table has one extra row and one extra column, so dp[i][j] is about s[i-1] and t[j-1].

LC 718 and LC 1143 side by side. One word in the problem statement, and everything below the third row changes:

Aspect	LC 718 · subarray	LC 1143 · subsequence
Contiguous?	Yes (a subarray)	No (a subsequence)
What dp[i][j] means	The common run that ends at A[i-1] and B[j-1]	The LCS of the first i and the first j characters
On a match	dp[i-1][j-1] + 1 (diagonal)	dp[i-1][j-1] + 1 (diagonal)
On a mismatch	Reset to 0 (the run is broken)	max(above, left) (skip one character)
Where the answer is	The maximum of the whole table	The bottom-right cell, dp[m][n]

Complexity, and the follow-up questions

There are (m+1)(n+1) states and each transition is O(1), so the time is O(mn) and the table itself is O(mn) space. The space can be reduced to O(min(m, n)) by keeping only one row, with the shorter string along the columns — but not for free. The transition also reads the diagonal dp[i-1][j-1], which a left-to-right pass overwrites before it is used, so that value must be saved in a temporary variable before the cell is assigned. Common follow-ups: (1) print the subsequence itself → walk backwards from the bottom-right cell; (2) what is LC 1035, uncrossed lines? → the same problem in different words, with no change to the code (see the problem set); (3) how does it differ from LC 718? → the mismatch row of the table above.

§05

Worked example C · edit distance

HARD

LC 72 — one cell, three source cells, and each one is a different operation.

The problem: turn word1 into word2. Each step may insert, delete, or replace one character. Find the fewest steps. For "horse" → "ros" the answer is 3.

The DP: the same table again. dp[i][j] = the fewest operations that turn the first i characters of word1 into the first j characters of word2. What is new is that a mismatch has three source cells instead of two. Stand on dp[i][j] and ask what the last operation was:

replace = dp[i-1][j-1] + 1delete = dp[i-1][j] + 1insert = dp[i][j-1] + 1

Replace: change the i-th character of word1 into the j-th character of word2. Both last characters are consumed at once, which leaves dp[i-1][j-1] — the cell on the diagonal.
Delete: remove the i-th character of word1. word1 gets one shorter and word2 is untouched, which leaves dp[i-1][j] — the cell above.
Insert: append the j-th character of word2 to word1. That character is now matched, so one more character of word2 is handled and word1 is otherwise unchanged, which leaves dp[i][j-1] — the cell on the left.

When the two last characters are already equal, no operation is needed: copy dp[i-1][j-1] without adding anything. Watch the three sources light up together on every mismatch:

LC 72 · filling the table cell by cell (mismatch: diagonal = replace, above = delete, left = insert)

∅

Turning word1 = "horse" (rows) into word2 = "ros" (columns). State: dp[i][j] is the fewest operations that turn the first i characters of word1 into the first j characters of word2. The base cases carry real meaning: dp[i][0] = i, because emptying a prefix of i characters takes i deletions, and dp[0][j] = j, because building j characters out of the empty string takes j insertions.

1 / 17

lc72_edit_distance.py

1class Solution:

2 def minDistance(self, a: str, b: str) -> int:

3 m, n = len(a), len(b)

4 dp = [[0] * (n + 1) for _ in range(m + 1)]

5 for i in range(m + 1):

6 dp[i][0] = i # delete all of a

7 for j in range(n + 1):

8 dp[0][j] = j # insert all of b

9 for i in range(1, m + 1):

10 for j in range(1, n + 1):

11 if a[i - 1] == b[j - 1]:

12 dp[i][j] = dp[i - 1][j - 1] # equal, no cost

13 else:

14 dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace

15 dp[i - 1][j], # delete

16 dp[i][j - 1]) # insert

17 return dp[m][n]

Python's min takes all three arguments at once, so the three operations fit on one expression. The three source cells are the diagonal, the one above, and the one on the left, matching the three highlighted cells in the animation.

In practice: spell checking and DNA alignment use this table

Edit distance, also called Levenshtein distance, is a general measure of how similar two sequences are. Search boxes and input methods use it to rank "did you mean …" suggestions. In bioinformatics, aligning DNA or protein sequences (the Needleman–Wunsch algorithm) is the same table with a score for each operation instead of a fixed cost of 1. Line-level git diffs, fuzzy finders such as fzf, and plagiarism checks all rest on this insert-delete-replace DP.

§06

Palindromes: expand outwards, or shrink inwards

MEDIUM

LC 5 / 516 / 647 / 132 — the last piece of subsequence DP, and the entry point to interval DP.

A palindrome reads the same forwards and backwards. There are two complementary ways to work with one:

View 1 · expand from a center

Try every center, move both ends outwards

A palindrome is symmetric about its center, so try all 2n−1 centers: n single characters for odd lengths and n−1 gaps between neighboring characters for even lengths. From each center, move outwards while the two ends match. O(n²) time, O(1) extra space. Best for substring problems, which need contiguity: LC 5, LC 647.

View 2 · interval DP

dp[i][j] describes one interval

dp[i][j] states something about the substring s[i..j]: whether it is a palindrome, or how long its longest palindromic subsequence is. The transition compares the two ends s[i] and s[j] and reads the shorter interval inside it, dp[i+1][j-1]. That dependency forces the iteration order: fill by increasing interval length, or let i run from high to low so that row i+1 is finished first. This is the entry point to interval DP in Chapter 10, and it is what LC 516 needs.

Start with expanding from a center, which LC 5 (longest palindromic substring) and LC 647 (counting palindromic substrings) both use:

Expanding from a center (s = "abcba", odd center at index 2)

center

An odd-length center: start at index 2, the letter "c". A single character is always a palindrome, so the length so far is 1.

1 / 4

lc5_longest_palindrome_substring.py

1class Solution:

2 def longestPalindrome(self, s: str) -> str:

3 res = ""

4 def expand(l: int, r: int) -> str:

5 while l >= 0 and r < len(s) and s[l] == s[r]:

6 l -= 1

7 r += 1

8 return s[l + 1 : r] # on exit [l+1, r-1] is the palindrome

9 for i in range(len(s)):

10 for cand in (expand(i, i), expand(i, i + 1)): # odd / even center

11 if len(cand) > len(res):

12 res = cand

13 return res

The slice s[l+1:r] is half-open on the right, which is exactly the palindrome range, so the length calculation disappears. Python slicing absorbs the off-by-one.

Now LC 516, the longest palindromic subsequence, from the interval DP side. There is a shortcut worth knowing: the longest palindromic subsequence of s is the longest common subsequence of s and reverse(s), so the code from the previous section solves it unchanged. Writing the interval DP directly also works, and it shows the iteration order that Chapter 10 is built on: i runs from high to low, j from low to high, because dp[i][j] reads dp[i+1][…].

lc516_longest_palindromic_subsequence.py

1class Solution:

2 def longestPalindromeSubseq(self, s: str) -> int:

3 n = len(s)

4 dp = [[0] * n for _ in range(n)]

5 for i in range(n - 1, -1, -1): # i from high to low

6 dp[i][i] = 1

7 for j in range(i + 1, n): # j from low to high

8 if s[i] == s[j]:

9 dp[i][j] = dp[i + 1][j - 1] + 2

10 else:

11 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

12 return dp[0][n - 1]

The one-line version: return LCS(s, s[::-1]), reusing LC 1143. A palindromic subsequence of s is a subsequence shared by s and its reverse.

Going further · LC 132, palindrome partitioning II

What happens when palindromes meet partitioning: cut the string into pieces so that every piece is a palindrome, using the fewest cuts. The approach is two DPs stacked. First, interval DP builds isPal[i][j], a table that answers "is s[i..j] a palindrome" in O(1). Then a one-dimensional DP over the cuts: dp[i] = min(dp[j] + 1) over every j for which s[j..i-1] is a palindrome. Building a lookup table first and running the main DP on top of it is a common combination, and worth practising once the main line feels stable.

§07

Problem set: 12 subsequence DP problems

Core set

Grouped as subsequence checking, LIS, contiguous, two sequences, and palindromes, from easier to harder. Think for 30 seconds before opening the hint.

LC 392Is SubsequenceSubsequenceTwo pointersDP optionalEASY

LC 300Longest Increasing SubsequenceSubsequenceLISBinary searchMEDIUM

LC 673Number of Longest Increasing SubsequenceLISCounting DPReviewMEDIUM

LC 718Maximum Length of Repeated SubarraySubarrayContiguous2D DPMEDIUM

LC 1143Longest Common SubsequenceTwo sequencesLCSDiagonal transitionMEDIUM

LC 1035Uncrossed LinesLCSRestated problemReviewMEDIUM

LC 583Delete Operation for Two StringsTwo sequencesLCSEdit distanceMEDIUM

LC 516Longest Palindromic SubsequencePalindromeInterval DPDiagonalMEDIUM

LC 5Longest Palindromic SubstringPalindromeExpand from centerReviewMEDIUM

LC 647Palindromic SubstringsPalindromeCountingExpand from centerMEDIUM

LC 72Edit DistanceTwo sequencesEdit distanceThree sourcesHARD

LC 132Palindrome Partitioning IIPalindromeDP on a lookup tableOptionalHARD

§08

Chapter quiz

✎ Quiz

Answer all 7 correctly to mark this chapter as complete.

QUESTION 01 / 7

What is the difference between a subsequence and a subarray (a substring)?

QUESTION 02 / 7

In the O(n²) solution to LC 300, dp[i] is defined as the length of the longest increasing subsequence ending at index i, rather than the longest one among the first i elements. Why?

QUESTION 03 / 7

Work it out by hand: for nums = [1, 3, 2, 4, 5], how long is the longest increasing subsequence?

QUESTION 04 / 7

Both LC 718 (maximum length of repeated subarray) and LC 1143 (longest common subsequence) fill a two-dimensional table. How do they differ when the two current characters are not equal?

QUESTION 05 / 7

Which of these statements about dp[i][j] in LC 1143 (longest common subsequence) are correct? (Select all that apply)

QUESTION 06 / 7

In LC 72 (edit distance), when word1[i-1] != word2[j-1] the transition is dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1. Which operation does each source cell stand for?

QUESTION 07 / 7

LC 516 asks for the longest palindromic subsequence. Which known problem can it be turned into directly?

What to take away from this chapter

The first fork: a subsequence may skip elements, a subarray or substring may not. Decide which one the problem wants before defining the state, because it decides whether a mismatch resets the cell to 0 or keeps the larger neighbor.
On a single sequence (LIS), anchor the subproblem by its last element: dp[i] is the length of the longest increasing subsequence ending at index i. The price of that choice is that the answer is the maximum of the whole array, not dp[n-1].
LIS drops from O(n²) to O(n log n) with tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k+1, plus a binary search. Its length is the answer; its contents are not a subsequence of the input.
The skeleton for two sequences: one table, one string along the rows and the other along the columns. A match always goes to the diagonal, dp[i-1][j-1]. All the differences between these problems are in the mismatch case.
The pair to remember: LC 718 resets to 0 on a mismatch (contiguous), LC 1143 takes max(above, left) (not contiguous), and LC 72 has one more source (diagonal = replace, above = delete, left = insert, take the smallest and add one).
Two views on palindromes: expand from a center (outwards, O(1) extra space, for substrings — LC 5, LC 647) and interval DP (inwards, dp[i][j], for subsequences — LC 516). Also, the longest palindromic subsequence of s is LCS(s, reverse(s)).
The iteration order comes from the transition. Interval DP reads dp[i+1][j-1], so i must run downwards or the table must be filled by increasing interval length. Complexity is (number of states) × (work per transition), and the table counts in the space. A rolling row is safe only when the transition reads the previous row alone; if it also reads the diagonal, save that value before overwriting the cell.
The most common bug in two-sequence DP is off-by-one indexing. The table has one extra row and column, so dp[i][j] is about s[i-1] and t[j-1], and the empty-string row and column must be filled first.