Unit 5.4 · about 4 h
122 / 324Sequence and string dynamic programming
One 2D table shape carries LCS, edit distance and their reductions. The mismatch branch decides which problem you solved.
- derive
- implement
You can now
- Derive the state, recurrence, base cases and order for prefix-pair and single-index sequence problems.
- Implement LCS, edit distance and quadratic LIS from blank files with differential tests.
- Tell subsequence, substring and edit variants apart by their mismatch branch.
Covers
- Sequence and string dynamic programming
Study, in this order
4 steps
- Two LIS recurrencesAlgorithms - dynamic programming
Section 3.6 (pp. 109-110): First Recurrence: Is This Next? (\(\operatorname{LISbigger}\), two indices) and Second Recurrence: What's Next? (\(\operatorname{LISfirst}\), one index, filled in decreasing order)
- Edit distance recurrence and tableAlgorithms - dynamic programming
Section 3.7 (pp. 111-114): \(\operatorname{Edit}(i, j)\) three-way recurrence, row-major order, and the ALGORITHM vs ALTRUISTIC table with distance 6
- Quadratic LIS with recoveryDSA Handbook - dynamic programming
The \(O(n^2)\) LIS: per-index \(\text{dp}[i]\) as \(\max\) over smaller predecessors, with parent-pointer recovery and the counting variants
- Prefix decisions with validity gatesDSA Handbook - dynamic programming
The recurrence, written once: \(\text{dp}[i]\) for the prefix
s[:i], a count of decodings for LC 91 Decode Ways and an OR over valid splits for LC 139 Word Break; Why \(\text{dp}[0] = \text{True}\), in one trace
Focus on
- \(\operatorname{LISfirst}\) runs on one index because starting here needs only later starts; \(\operatorname{LISbigger}\) needs two indices because skipping is relative to a threshold.
- Edit distance has three predecessors because the last column has three shapes. LCS mismatch only skips one side, which is an up or left step.
- Subsequence inherits \(\max(\text{up}, \text{left})\) on mismatch; substring resets to 0. On ABCBDAB and BDCAB the answers are 4 and 2.
- Decode Ways and Word Break share one skeleton: \(\text{dp}[i]\) combines the valid splits that end at \(i\), a sum for Decode Ways and an OR for Word Break, each gated by a validity predicate.
Reproduce closed-book
Traps
- Running LCS code on a longest-common-substring ask. Same table shape, different mismatch branch; the corner cell is not the substring answer.
- Forgetting \(\text{max-empty} = 0\) in \(\operatorname{LISfirst}\). Then \(\operatorname{LISfirst}(n)\) needs a special base case instead of falling out of the recurrence.
- Counting 06 as one decoding in Decode Ways. A leading zero is invalid; gate 0 and out-of-range pairs to zero.
Practice
LeetCode 1143 - Longest Common Subsequence
Attempt cold. Check \((\text{abcde}, \text{ace}) = 3\), \((\text{abc}, \text{abc}) = 3\), \((\text{abc}, \text{def}) = 0\), then submit.
Attempt cold: write state, transition, base case and order first. After submitting, read the AlgoMaster Longest Common Subsequence lesson (https://algomaster.io/learn/dsa/longest-common-subsequence).
LeetCode 300 - Longest Increasing Subsequence
Check \([10,9,2,5,3,7,101,18] = 4\) and \([7,7,7,7,7,7,7] = 1\), then submit.
After submitting, compare with the DSA Handbook lis-quadratic page, including the strict-increase gate.
Self-test
-
State the \(\operatorname{LISfirst}\) recurrence and why decreasing order works.
\(\operatorname{LISfirst}(i) = 1 + \max\) of \(\operatorname{LISfirst}(j)\) over \(j > i\) with \(A[j] > A[i]\), with \(\text{max-empty} = 0\). Entry \(i\) reads only entries \(j > i\), so filling \(i\) from \(n\) down keeps every read on a computed cell. -
Why does edit distance need the diagonal predecessor while LCS mismatch does not?
Substitution consumes one character from each string in a single column, which is exactly the diagonal step with cost \([A[i] \ne B[j]]\). LCS mismatch only skips a character from one side, which is an up or left step. -
Word Break on
catsandogwith[cats, dog, sand, and, cat]: what does \(\text{dp}\) say and why?False. No valid split covers the string: the \(\text{dp}[i]\) OR over splits finds no chain of dictionary words reaching position 9. -
When do you prefer the two-index \(\operatorname{LISbigger}\) over \(\operatorname{LISfirst}\)?
Rarely for code; \(\operatorname{LISfirst}\) is shorter and \(O(n)\) space. \(\operatorname{LISbigger}\) earns its keep only when the threshold value matters per state, and both are \(O(n^2)\) time.
Completion criterion
Stop when
The reproduce numbers come out of a blank file, the brute-force differential tests pass, and you can call the mismatch branch for subsequence versus substring without notes.
Mark passed, then open 5.5 Only mark this when you can do it without notes.Leads to
- 5.5 Grid, path and interval dynamic programming Move the prefix-pair machinery to grids and intervals.
- 5.8 Recurrence proofs and differential validation Prove the string recurrences and validate them against brute force.
Comes after
- 2.7 Tries and prefix lookupPrefix structure reappears in string dynamic programming.
- 5.2 Memoization, tabulation and dependency orderApply both evaluation forms to two-index recurrences.
- 5.3 Solution reconstruction and rolling stateRecover witnesses on the string table where ties create several valid answers.
Resources for this unit
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
Also in this section
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs. - Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.