Dynamic Programming II: Sequences and Intervals
Chapter 28: Dynamic Programming II โ Sequences and Intervals
In the previous chapter we laid the groundwork with one-dimensional DP and knapsack problems. This chapter raises the stakes: when the problem involves the relationship between two sequences or an optimal solution over a contiguous interval within a single sequence, the state space grows from one dimension to two. The DP table becomes a matrix, and understanding the order in which you fill that matrix is the key to mastering this class of problems.
Sequence DP and interval DP are the two most frequently tested DP subcategories in technical interviews. They share a common signature: the state is defined by two indices i and jโone marking the row, the other marking the column of your DP matrix. Once you see how a cell depends on its neighbors, the rest follows.
Level 1 ยท What You Need to Know
28.1 Longest Common Subsequence (LCS)
Problem Statement
Given two strings text1 and text2, find the length of their longest common subsequence. A subsequence does not need to be contiguous but must preserve relative order.
Example: text1 = "abcde", text2 = "ace". The LCS is "ace", length 3.
State Definition
dp[i][j] = length of the LCS of text1[0..i-1] and text2[0..j-1].
The index offset is intentional: by letting dp[0][*] and dp[*][0] represent the empty prefix, we get a natural base case of 0 without special handling.
Transition
If text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # characters match, extend LCS
Else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # drop one character from either string
Implementation
def longest_common_subsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
Time O(mn), space O(mn).
Recovering the Actual LCS
Knowing the length is not always enoughโinterviewers often ask you to reconstruct the LCS string itself. Start at dp[m][n] and trace back toward dp[0][0]:
def get_lcs(text1: str, text2: str) -> str:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Backtrack from bottom-right
i, j = m, n
result = []
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
result.append(text1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
Backtracking logic:
- If the current characters in both strings are the same, this character belongs to the LCS. Record it and move diagonally.
- Otherwise, move in the direction of the larger dp value.
Worked Example
For text1 = "ABCBDAB", text2 = "BDCAB", the completed DP table and backtracking yield LCS = "BCAB" (length 4):
"" B D C A B
"" 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4
28.2 Longest Common Substring
How It Differs from LCS
- Subsequence: not required to be contiguous.
- Substring: must be contiguous.
The state definition changes: dp[i][j] = length of the longest common substring ending at text1[i-1] and text2[j-1].
Transition
If text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
Else:
dp[i][j] = 0 # mismatch resets to zero
The answer is the maximum value in the entire dp table.
def longest_common_substring(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
max_len = max(max_len, dp[i][j])
# else: dp[i][j] remains 0
return max_len
Comparison Table
| Property | LCS (subsequence) | Longest Common Substring |
|---|---|---|
| Contiguity | Not required | Required |
| On mismatch | Take max of left/above | Reset to 0 |
| Answer location | dp[m][n] | Global max over entire table |
| Time complexity | O(mn) | O(mn) |
28.3 Edit Distance (Levenshtein Distance)
Problem Statement (LeetCode #72)
Given two strings word1 and word2, find the minimum number of operations to convert word1 into word2. Three operations are allowed:
- Insert a character
- Delete a character
- Replace a character
State Definition
dp[i][j] = minimum number of operations to convert word1[0..i-1] into word2[0..j-1].
Base Cases
dp[0][j] = j: turning the empty string into a string of length j requires j insertions.dp[i][0] = i: turning a string of length i into the empty string requires i deletions.
Transition
If word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # characters match, no operation needed
Else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete word1[i-1]
dp[i][j-1], # insert word2[j-1]
dp[i-1][j-1] # replace word1[i-1] with word2[j-1]
)
Implementation
def min_distance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # delete
dp[i][j - 1], # insert
dp[i - 1][j - 1] # replace
)
return dp[m][n]
Worked Example
Convert "horse" to "ros":
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
Answer: 3 (replace h with r, delete r, delete e).
Interpreting the Three Operations on the Grid
In the DP table, the three operations correspond to three directions:
dp[i-1][j] + 1(from above) = delete word1[i-1]dp[i][j-1] + 1(from the left) = insert word2[j-1]dp[i-1][j-1] + 1(from the diagonal) = replace
Think of it this way: you are finding a path from (0,0) to (m,n) in the DP grid, and each step you take corresponds to an edit operation.
28.4 Palindromic Substrings
Problem Statement (LeetCode #647)
Given a string s, count the number of palindromic substrings.
State Definition
dp[i][j] = whether s[i..j] (inclusive on both ends) is a palindrome.
Transition
dp[i][j] = True if and only if:
s[i] == s[j] AND (j - i <= 2 OR dp[i+1][j-1] == True)
j - i <= 2: substrings of length 1 (single character), length 2 (two identical characters), or length 3 (ends match, middle is anything) can be directly determined.- Otherwise, the inner substring
s[i+1..j-1]must also be a palindrome.
Fill Order
Since dp[i][j] depends on dp[i+1][j-1] (a cell with a larger row index and smaller column index), we must fill either bottom-to-top, left-to-right or by increasing substring length.
def count_substrings(s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and (length <= 3 or dp[i + 1][j - 1]):
dp[i][j] = True
count += 1
return count
Time O(n^2), space O(n^2).
Expand-Around-Center (better constant factor)
In practice, the center-expansion approach is more common in interviews, using O(1) space:
def count_substrings_expand(s: str) -> int:
n = len(s)
count = 0
def expand(left: int, right: int) -> int:
cnt = 0
while left >= 0 and right < n and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
for i in range(n):
count += expand(i, i) # odd length
count += expand(i, i + 1) # even length
return count
28.5 Longest Palindromic Subsequence
Problem Statement (LeetCode #516)
Given a string s, find the length of the longest palindromic subsequence. Note: subsequence, not substringโcontiguity is not required.
State Definition
dp[i][j] = length of the longest palindromic subsequence in s[i..j].
Transition
If s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2 # both ends match, include them
Else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) # drop either the left end or the right end
Base Case
dp[i][i] = 1 (a single character is a palindrome of length 1).
def longest_palindrome_subseq(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
Relationship with LCS
The longest palindromic subsequence of s equals the LCS of s and reverse(s). This gives an alternative solution, though the interval DP approach above is more direct.
Level 2 ยท What You Should Master
28.6 Interval DP Template
What Is Interval DP?
Interval DP defines a state dp[i][j] representing the optimal solution for the interval [i, j]. Its hallmark is that the answer for a large interval depends on trying every possible "split point" that divides it into two smaller intervals.
General Template
def interval_dp(arr):
n = len(arr)
dp = [[0] * n for _ in range(n)]
# Base case: intervals of length 1
for i in range(n):
dp[i][i] = base_case(i)
# Enumerate by increasing length
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf') # or -inf for maximization
for k in range(i, j): # try each split point
dp[i][j] = min(
dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, j, k)
)
return dp[0][n - 1]
Three nested loops: outer for length, middle for starting position, inner for split point. Time O(n^3).
28.7 Matrix Chain Multiplication
Problem
Given n matrices A1, A2, ..., An where matrix Ai has dimensions p[i-1] x p[i], find the parenthesization that minimizes the total number of scalar multiplications.
State Definition
dp[i][j] = minimum number of scalar multiplications needed to compute Ai x Ai+1 x ... x Aj.
Transition
dp[i][j] = min over k in [i, j-1] of:
dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
The term p[i-1] * p[k] * p[j] is the cost of multiplying the two resulting matrices.
def matrix_chain_order(p: list) -> int:
"""
p: dimension array of length n+1. Matrix Ai has dimensions p[i-1] x p[i].
Returns minimum number of scalar multiplications.
"""
n = len(p) - 1
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
dp[i][j] = min(dp[i][j], cost)
return dp[1][n]
# Example: 4 matrices with dimensions [30x35, 35x15, 15x5, 5x10]
p = [30, 35, 15, 5, 10]
print(matrix_chain_order(p)) # Output: 15125
28.8 Burst Balloons (LeetCode #312)
Problem
You have n balloons numbered 0 to n-1. Each balloon has a number nums[i]. Bursting balloon i earns nums[left] * nums[i] * nums[right] coins (where left and right are the adjacent balloons after i is burst). Find the maximum coins you can collect.
Key Insight: Think in Reverse
Thinking forward (which to burst first) makes it hard to define subproblems because boundaries change after each burst. Think backward instead: which balloon is burst last in a given interval?
If balloon k is the last to be burst in the interval [i, j], then at that moment its left boundary is i-1 and its right boundary is j+1 (because everything else in [i, j] is already gone).
Implementation
Add virtual balloons with value 1 at both ends, then apply interval DP:
def max_coins(nums: list) -> int:
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
# dp[i][j] = max coins from bursting all balloons in open interval (i, j)
for length in range(2, n):
for i in range(n - length):
j = i + length
for k in range(i + 1, j): # k is the last balloon burst
coins = nums[i] * nums[k] * nums[j]
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins)
return dp[0][n - 1]
Note the open interval convention: dp[i][j] covers balloons strictly between i and j. When k is the last to be burst, its neighbors are i and j.
Time O(n^3), space O(n^2).
28.9 Space Optimization for Edit Distance
The standard edit distance algorithm uses O(mn) space. Observe the transition: dp[i][j] depends only on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]โonly the current row and the previous row are needed.
def min_distance_optimized(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# Ensure word2 is the shorter one to minimize space
if m < n:
return min_distance_optimized(word2, word1)
prev = list(range(n + 1))
curr = [0] * (n + 1)
for i in range(1, m + 1):
curr[0] = i
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
prev, curr = curr, prev
return prev[n]
Space drops from O(mn) to O(min(m, n)).
Further Optimization: Single Row + One Variable
def min_distance_one_row(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
if m < n:
return min_distance_one_row(word2, word1)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev_diag = dp[0] # saves dp[i-1][j-1]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j] # saves dp[i-1][j] before overwrite
if word1[i - 1] == word2[j - 1]:
dp[j] = prev_diag
else:
dp[j] = 1 + min(dp[j], dp[j - 1], prev_diag)
prev_diag = temp
return dp[n]
Space O(min(m, n)) with a single array and one extra variable.
28.10 O(n log n) Optimization of LCS via LIS
When elements are distinct (or one sequence is a permutation), the LCS problem can be reduced to the Longest Increasing Subsequence (LIS) problem, improving from O(mn) to O(n log n).
Reduction Idea
- For each character in
text2, record all positions where it appears intext1(in reverse order to ensure correctness). - Concatenate all these positions into a single sequence.
- Find the LIS of this sequence.
Why Does This Work?
Two characters are matched in the LCS if and only if their positions in both sequences are in increasing order. Once we map each character of text2 to its positions in text1, finding the longest increasing subsequence of those positions is equivalent to finding the LCS.
import bisect
def lcs_via_lis(text1: str, text2: str) -> int:
"""
General approach when characters may repeat.
Reduces LCS to LIS.
"""
from collections import defaultdict
pos = defaultdict(list)
for i in range(len(text1) - 1, -1, -1):
pos[text1[i]].append(i)
# Build sequence: positions in text1 for each char of text2
sequence = []
for char in text2:
if char in pos:
sequence.extend(pos[char])
# LIS via patience sorting
tails = []
for num in sequence:
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
tails.append(num)
else:
tails[idx] = num
return len(tails)
When both sequences have similar length and the alphabet is small, this can be significantly faster than O(mn).
Level 3 ยท What Sets You Apart
28.11 The History of Edit Distance
Edit distance was first defined by Soviet mathematician Vladimir Levenshtein in his 1965 paper "Binary codes capable of correcting deletions, insertions, and reversals." His original motivation was information theory: if a message undergoes character insertions, deletions, or substitutions during transmission, the receiver needs to quantify how "far" the corrupted message is from the original.
Although Levenshtein defined the distance metric, he did not provide an efficient algorithm to compute it. The first O(mn) dynamic programming algorithm was given by Robert Wagner and Michael Fischer in their 1974 paper "The String-to-String Correction Problem." For this reason, the DP approach is sometimes called the Wagner-Fischer algorithm.
28.12 Edit Distance in NLP and Bioinformatics
Spell Correction
The earliest spell-correction systems (1960s-70s) were built directly on edit distance. Given a misspelled word, search the dictionary for the word with the smallest edit distance. Peter Norvig wrote a famous 21-line Python spell corrector whose core is generating candidates at edit distance 1 and 2.
Modern spell correction uses more sophisticated models (e.g., the noisy channel model), but edit distance remains a foundational component.
DNA Sequence Alignment
Sequence alignment in bioinformatics is essentially a variant of edit distance. The Needleman-Wunsch algorithm (1970) performs global alignment; the Smith-Waterman algorithm (1981) performs local alignment. Both are O(mn) DP algorithms differing in:
- Needleman-Wunsch: initialization and transitions are nearly identical to standard edit distance, but with a substitution matrix (scoring matrix) instead of simple 0/1 costs.
- Smith-Waterman: allows alignment to start and end anywhere; dp values are clamped to be non-negative (
max(0, ...)); the final answer is the global maximum in the dp table rather than dp[m][n].
BLAST (Basic Local Alignment Search Tool) is the most widely used tool in bioinformatics. It is essentially a heuristic speedup of Smith-Waterman.
Applications in Natural Language Processing
- Machine Translation Evaluation: WER (Word Error Rate) is the word-level edit distance divided by the reference sentence length.
- Information Extraction: Entity matching uses edit distance to determine whether two names refer to the same entity (e.g., "Jon Snow" vs. "John Snow").
- Fuzzy Search: Database functions like
SOUNDEX,LEVENSHTEIN()are built on edit distance.
28.13 The Myers Diff Algorithm
The Core of Git Diff
When you run git diff, Git uses the algorithm from Eugene Myers' 1986 paper "An O(ND) Difference Algorithm and Its Variations." The time complexity is O(ND), where N is the total length of the two files and D is the size of the minimum edit (the diff size).
Core Idea
Myers' algorithm transforms the diff problem into a shortest-path problem on a graph:
- Construct an (m+1) x (n+1) edit graph.
- Every path from (0,0) to (m,n) corresponds to one way of editing.
- Horizontal moves = deletions, vertical moves = insertions, diagonal moves = matches (zero cost).
- Goal: find the path from (0,0) to (m,n) with the fewest non-diagonal moves.
Algorithm Sketch
For d = 0, 1, 2, ...:
For each diagonal k = -d, -d+2, ..., d:
Advance as far as possible along the diagonal (greedily: matching characters are free)
If we reach (m, n), return d
When the two files are nearly identical (D is small), the algorithm runs in near-linear time. This is why git diff is typically fastโmost commits change only a few lines.
Relationship to Standard DP
Myers' algorithm is essentially BFS on the edit graph of Levenshtein DP, exploiting the fact that diagonal moves are free. It computes "edit distance with only insertions and deletions" (no replacements), which is exactly what diff needs: a line is either kept, deleted, or inserted.
28.14 The Wagner-Fischer Algorithm Formalized
Wagner and Fischer's 1974 paper made the following contributions:
-
Proved optimal substructure: if the last operation in the optimal edit sequence from word1 to word2 is operation X, then removing that last step yields an optimal sequence for the corresponding subproblem.
-
Proved correctness: by induction on i + j, dp[i][j] equals the minimum edit distance from word1[0..i-1] to word2[0..j-1].
-
Generalized the cost model: different operations can have different costs w(a -> b), as long as the cost function satisfies metric properties (non-negativity, symmetry, triangle inequality).
28.15 Interval DP and Optimal Binary Search Trees (Knuth's Optimization)
Optimal BST Problem
Given n ordered keys k1 < k2 < ... < kn, each with search probability pi, construct a BST that minimizes the expected search cost.
This is a classic interval DP problem:
dp[i][j] = minimum expected cost of the optimal BST for keys ki, ..., kj
dp[i][j] = min over r in [i, j] of:
dp[i][r-1] + dp[r+1][j] + sum(p[i..j])
The naive implementation is O(n^3). However, Donald Knuth proved in 1971 a key monotonicity property: letting root[i][j] be the optimal root for dp[i][j]:
root[i][j-1] <= root[i][j] <= root[i+1][j]
The optimal split point is monotone. Exploiting this, the inner loop no longer needs to scan all possible k values, reducing total time from O(n^3) to O(n^2).
When Knuth's Optimization Applies
Knuth's optimization applies to interval DP when the cost function w(i, j) satisfies:
- Monotonicity on the lattice of intervals:
w(a, c) + w(b, d) <= w(a, d) + w(b, c)for alla <= b <= c <= d. - Quadrangle inequality:
w(i, j)satisfies the quadrangle inequality.
When both hold, the optimal split point root[i][j] is monotone, enabling the O(n^3) to O(n^2) speedup.
def optimal_bst(p: list, n: int) -> float:
"""
p[1..n]: search probabilities.
Returns minimum expected search cost.
"""
prefix_sum = [0] * (n + 2)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + p[i]
def w(i, j):
return prefix_sum[j] - prefix_sum[i - 1]
dp = [[0.0] * (n + 2) for _ in range(n + 2)]
root = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
dp[i][i] = p[i]
root[i][i] = i
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for r in range(root[i][j - 1], root[i + 1][j] + 1):
cost = dp[i][r - 1] + dp[r + 1][j] + w(i, j)
if cost < dp[i][j]:
dp[i][j] = cost
root[i][j] = r
return dp[1][n]
Level 4 ยท Practical Pitfalls and Interview Favorites
28.16 Boundary Condition Traps in Edit Distance
Edit distance looks straightforward, but many candidates stumble on boundary conditions in interviews:
Trap 1: Forgetting to Initialize Row 0 and Column 0
# Wrong: forgetting initialization
dp = [[0] * (n + 1) for _ in range(m + 1)]
# dp[i][0] and dp[0][j] are all 0 โ incorrect!
# Correct
for i in range(m + 1):
dp[i][0] = i # i deletions
for j in range(n + 1):
dp[0][j] = j # j insertions
Trap 2: Empty String Handling
When word1 or word2 is empty, the answer is simply the length of the other string. If you special-case if not word1: return len(word2), that is fine. But if you rely on the DP table, you must ensure your initialization correctly handles this case.
Trap 3: Index Offset
dp[i][j] corresponds to word1[0..i-1] and word2[0..j-1]. In the transition, you compare word1[i-1] and word2[j-1], not word1[i] and word2[j]. This off-by-one error is extremely common.
28.17 The Relationship Between LCS and Edit Distance
This is an important mathematical identity:
Let
word1have length m,word2have length n, their LCS length be L, and the edit distance using only insertions and deletions (no replacements) be d. Then:d = m + n - 2L
Proof
The L characters in the LCS are the ones that "stay put." The m - L characters in word1 not in the LCS must be deleted; the n - L characters in word2 not in the LCS must be inserted. Total operations = (m - L) + (n - L) = m + n - 2L.
Practical Implications
- With only insertions and deletions (no replacement): edit distance = m + n - 2 * LCS.
- With replacements allowed: Levenshtein distance <= m + n - 2 * LCS (because one replacement can substitute for one deletion + one insertion).
LeetCode #583 (Delete Operation for Two Strings) directly tests this relationship.
28.18 High-Frequency Sequence DP Interview Problems
Distinct Subsequences (LeetCode #115)
Given strings s and t, count the number of distinct subsequences of s that equal t.
def num_distinct(s: str, t: str) -> int:
m, n = len(s), len(t)
# dp[i][j] = number of subsequences of s[0..i-1] that equal t[0..j-1]
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base case: empty t matches any prefix of s exactly once
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j] # skip s[i-1]
if s[i - 1] == t[j - 1]:
dp[i][j] += dp[i - 1][j - 1] # use s[i-1] to match t[j-1]
return dp[m][n]
Interleaving String (LeetCode #97)
Given three strings s1, s2, s3, determine whether s3 is formed by interleaving s1 and s2.
def is_interleave(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
# dp[i][j] = can s1[:i] + s2[:j] interleave to form s3[:i+j]?
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (
(dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or
(dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
)
return dp[m][n]
Regular Expression Matching (LeetCode #10)
Implement regex matching with . and *. . matches any single character; * matches zero or more of the preceding element.
def is_match(s: str, p: str) -> bool:
m, n = len(s), len(p)
# dp[i][j] = does s[0..i-1] match p[0..j-1]?
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Base case: empty s, pattern like x*y*z* can match
for j in range(2, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
# * matches zero of the preceding element
dp[i][j] = dp[i][j - 2]
# * matches one or more
if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
dp[i][j] = dp[i][j] or dp[i - 1][j]
elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
Key insight: * has two choicesโmatch zero of the preceding character (jump left by 2: dp[i][j-2]) or match one more (move up: dp[i-1][j], because * can keep matching).
Wildcard Matching (LeetCode #44)
Implement wildcard matching with ? and *. ? matches any single character; * matches any sequence of characters (including empty).
def is_match_wildcard(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Leading *'s can match empty string
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
# * matches empty (dp[i][j-1]) or matches current char (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
Regex vs. WildcardโKey Differences:
| Property | Regex (#10) | Wildcard (#44) |
|---|---|---|
* meaning |
Repeat preceding char 0+ times | Match any string |
* independence |
Cannot stand alone; must follow a character | Stands alone |
| Initialization | dp[0][j]: check x* patterns | dp[0][j]: check leading * prefix |
28.19 Stock Trading Series (State Machine DP)
The stock trading series is a classic application of state machine DP. Core idea: define the state to include not just the day i, but also whether you currently hold stock and how many transactions you have completed.
General Framework
Define:
dp[i][k][0]= max profit on day i, at most k transactions completed, not holding stockdp[i][k][1]= max profit on day i, at most k transactions completed, holding stock
Transitions:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
# held no stock yesterday # sell today
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
# held stock yesterday # buy today (uses one transaction)
Best Time to Buy and Sell Stock II (LeetCode #122) โ Unlimited Transactions
With k = infinity, k and k-1 are indistinguishable:
def max_profit_ii(prices: list) -> int:
n = len(prices)
dp_cash, dp_hold = 0, -prices[0]
for i in range(1, n):
dp_cash = max(dp_cash, dp_hold + prices[i])
dp_hold = max(dp_hold, dp_cash - prices[i])
return dp_cash
Best Time to Buy and Sell Stock III (LeetCode #123) โ At Most Two Transactions
def max_profit_iii(prices: list) -> int:
buy1 = buy2 = -float('inf')
sell1 = sell2 = 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2
Best Time to Buy and Sell Stock IV (LeetCode #188) โ At Most k Transactions
def max_profit_iv(k: int, prices: list) -> int:
n = len(prices)
if not prices or k == 0:
return 0
# If k >= n//2, equivalent to unlimited transactions
if k >= n // 2:
return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))
# dp[j][0]: at most j transactions, not holding
# dp[j][1]: at most j transactions, holding
dp = [[0, -float('inf')] for _ in range(k + 1)]
for price in prices:
for j in range(1, k + 1):
dp[j][0] = max(dp[j][0], dp[j][1] + price)
dp[j][1] = max(dp[j][1], dp[j - 1][0] - price)
return dp[k][0]
With Cooldown (LeetCode #309)
After selling, you cannot buy on the next day. Add a "frozen" state:
def max_profit_cooldown(prices: list) -> int:
n = len(prices)
if n <= 1:
return 0
# Three states: holding, cash (not frozen), frozen
hold = -prices[0]
cash = 0
frozen = 0
for i in range(1, n):
new_hold = max(hold, cash - prices[i]) # can only buy from cash (not frozen)
new_cash = max(cash, frozen) # stay in cash or thaw from frozen
new_frozen = hold + prices[i] # sell -> enter frozen
hold, cash, frozen = new_hold, new_cash, new_frozen
return max(cash, frozen)
State Machine Diagram
buy
cash โโโโโโโโโโโบ hold
^ |
| thaw | sell
| v
frozen <โโโโโโโโโโ (on sell)
28.20 Summary: Mental Map for Sequence and Interval DP
Sequence DP
โโโ Two sequences
โ โโโ LCS: dp[i][j] = LCS length of first i and first j chars
โ โโโ Edit Distance: dp[i][j] = min cost to transform word1[:i] โ word2[:j]
โ โโโ Interleaving String: dp[i][j] = can s1[:i] + s2[:j] form s3[:i+j]?
โ โโโ Regex/Wildcard Matching: dp[i][j] = does s[:i] match p[:j]?
โโโ Single sequence
โ โโโ Palindromic Substrings: dp[i][j] = is s[i..j] a palindrome?
โ โโโ Longest Palindromic Subsequence: dp[i][j] = LPS length in s[i..j]
โ โโโ Distinct Subsequences: dp[i][j] = count of subsequences of s[:i] equal to t[:j]
โโโ State Machine DP
โโโ Stock Trading: dp[i][k][state] = max profit on day i, k transactions, given state
Interval DP
โโโ Template: dp[i][j] = optimal for interval [i,j], enumerate split point k
โโโ Matrix Chain Multiplication
โโโ Burst Balloons: open-interval definition, think in reverse
โโโ Optimal BST + Knuth's Optimization: O(nยณ) โ O(nยฒ)
โโโ Palindrome problems (also interval DP)
Interview Advice
- When you encounter a sequence DP problem, pin down the precise meaning of
dp[i][j]โdoes it represent "first i characters" or "ending at index i"? - The signature of interval DP: the problem asks for an optimal solution over a "contiguous range," and larger ranges can be solved by splitting into smaller ones.
- Regex/wildcard matching are variants of edit distanceโthey all involve two-sequence DP, just with different transition rules.
- The stock series may not look like sequence DP, but it is textbook state machine DP. Draw out all possible states (holding/not holding/frozen/transaction count) and the transitions become clear.