Classic DP: LIS, LCS, and Edit Distance

Dynamic programming is recursion with a memory: instead of recomputing the same subproblem thousands of times, you solve each subproblem once and store the answer in a table. The three problems in this lesson all share the same DNA — the state is a prefix (or a pair of prefixes) of one or two sequences — which is why mastering them unlocks a huge slice of interview and competitive-programming DP.

What you’ll learn

Longest Increasing Subsequence (LIS): the $O(n^2)$ table version, and the $O(n \log n)$ patience-sorting version built on bisect_left.
Longest Common Subsequence (LCS): the 2D recurrence, and how the table itself encodes the alignment between two sequences.
Edit Distance (Levenshtein distance): LCS’s cousin, adding insert, delete, and replace as first-class transitions.
How to go from “just the length” to reconstructing the actual answer by walking the table backward.

The cue

The input is one or two sequences and the question asks for the longest / shortest / cheapest way to align, transform or select from them — and the answer is a number, not a specific arrangement.
The choice at each position is local and small (“take this character or not”, “extend this run or not”), but the consequences are not — a greedy choice can be locally optimal and globally wrong.
You can phrase the answer for a prefix in terms of answers for shorter prefixes. That phrasing is the recurrence; everything after it is bookkeeping.

Reach for something else when the required subsequence must be contiguous (that is a sliding window or Kadane’s, both $O(n)$ — do not pay $O(n^2)$ for it), when a greedy exchange argument provably works (interval scheduling), or when the state is a range [i, j] rather than a prefix (that is DP on Grids and Intervals).

Longest Increasing Subsequence

Define dp[i] as the length of the longest increasing subsequence that ends exactly at index i. To extend a subsequence ending at some earlier index j up to i, you need nums[j] < nums[i] — so dp[i] looks back at every smaller-valued predecessor and takes the best one:

dp[i] = 1 + \max_{\substack{j < i \\ nums[j] < nums[i]}} dp[j] \qquad \big(dp[i] = 1 \text{ if no such } j \text{ exists}\big)

The answer is max(dp), since the longest subsequence can end anywhere.

lis_On2.py

def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n   # dp[i] = length of the LIS ending exactly at index i
 
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)
 
 
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))   # expect 4  ([2, 3, 7, 18] or [2, 3, 7, 101])

Step the table fill. The two rows are the input and dp; the dashed arrow shows which dp[j] the current dp[i] is reading:

dpEvery dp[i] looks back at every smaller predecessorLC 300 · O(n^2)

cols: index

1def lis(arr):2    dp = [1] * len(arr)          # every element alone is a run of 13    for i in range(len(arr)):4        for j in range(i):5            if arr[j] < arr[i]:6                dp[i] = max(dp[i], dp[j] + 1)7    return max(dp, default=0)

base casedp[i] is the length of the longest increasing subsequence *ending at* i. Every element is a valid run of length 1 on its own, so that is the floor.

1/30

Scrub to the last frame and note that the answer is max(dp), NOT dp[-1]. The longest run does not have to end at the final element -- returning dp[-1] is the single most common wrong answer on LC 300.

That’s $O(n^2)$ — fine up to a few thousand elements, but too slow once n reaches the hundreds of thousands. There’s a faster way that drops the inner loop entirely.

The O(n log n) trick: patience sorting

Keep an array tails where tails[k] is the smallest possible tail value among all increasing subsequences of length k + 1 found so far. tails is always sorted, which means you can binary search it: for each new number x, find the leftmost slot where x could sit (bisect_left), and either extend tails (if x is bigger than everything) or overwrite that slot with the smaller, more promising tail value.

lis_Onlogn.py

from bisect import bisect_left
 
def length_of_lis_fast(nums):
    tails = []   # tails[k] = smallest tail value of an increasing subsequence of length k + 1
 
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)     # x extends the longest subsequence found so far
        else:
            tails[i] = x         # x gives a smaller tail for length i + 1 -- better future potential
 
    return len(tails)
 
 
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis_fast(nums))   # expect 4

sketch Patience piles: scanning [10, 9, 2, 5, 3, 7, 101, 18] p5.js

Each bar is a slot in tails. A new value either extends the array (a new pile) or overwrites the first slot it's small enough to replace, keeping every pile's tail as small as possible.

Longest Common Subsequence

LCS asks: what’s the longest sequence of characters (not necessarily contiguous) that appears, in order, in both text1 and text2? The state is a pair of prefix lengths (i, j), and the recurrence branches on whether the last characters of each prefix match:

dp[i][j] = \begin{cases} 0 & i = 0 \text{ or } j = 0 \\ dp[i-1][j-1] + 1 & text1[i-1] = text2[j-1] \\ \max\big(dp[i-1][j],\ dp[i][j-1]\big) & \text{otherwise} \end{cases}

longest_common_subsequence.py

def longest_common_subsequence(text1, text2):
    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]
 
 
print(longest_common_subsequence("abcde", "ace"))   # expect 3  ("ace")

dpA match reads the diagonal; a mismatch takes the better neighbourLC 1143 · O(m x n)

rows: a = "ABCBDAB"cols: b = "BDCABA"

1def lcs(a, b):2    m, n = len(a), len(b)3    dp = [[0] * (n + 1) for _ in range(m + 1)]4    for i in range(1, m + 1):5        for j in range(1, n + 1):6            if a[i - 1] == b[j - 1]:7                dp[i][j] = dp[i - 1][j - 1] + 1     # diagonal + 18            else:9                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])10    return dp[m][n]

base caseRow 0 and column 0 are all zeros: the longest common subsequence with an empty string is empty. Those sentinels are why the loops can start at 1 and never test for out-of-range indices.

1/86

Watch the dependency arrows. A match has ONE dependency (the diagonal) because both characters are consumed together. A mismatch has TWO, because we do not know which string to advance -- so we try both and keep the better. The final frame highlights the traced-back subsequence.

Delete Operation for Two Strings is LCS in disguise: the minimum number of deletions to make two strings equal is m + n - 2 * lcs_length, since every character not in the LCS from either string must be deleted.

Edit Distance (Levenshtein distance)

Edit Distance generalizes LCS by allowing three operations — insert, delete, and replace — each costing 1. The recurrence adds a min over all three when characters don’t match:

dp[i][j] = \begin{cases} j & i = 0 \\ i & j = 0 \\ dp[i-1][j-1] & word1[i-1] = word2[j-1] \\ 1 + \min\big(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]\big) & \text{otherwise} \end{cases}

Reading the three terms as delete, insert, replace: dp[i-1][j] deletes a character from word1, dp[i][j-1] inserts a character to match word2, and dp[i-1][j-1] replaces one character for another.

dpThree arrows on a mismatch, one on a matchLC 72 · O(m x n)

rows: from "horse"cols: to "ros"

1def edit_distance(a, b):2    m, n = len(a), len(b)3    dp = [[0] * (n + 1) for _ in range(m + 1)]4    for i in range(m + 1): dp[i][0] = i     # delete everything5    for j in range(n + 1): dp[0][j] = j     # insert everything6    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]          # free10            else:11                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace12                                   dp[i - 1][j],      # delete13                                   dp[i][j - 1])      # insert14    return dp[m][n]

base caseThe edges are not zeros here. Turning a prefix of length i into the empty string costs i deletions, and the reverse costs j insertions — so row 0 and column 0 count up. Getting these wrong is the usual reason an edit-distance solution is off by a constant.

1/32

The base row and column are NOT zeros here -- they count up, because turning a prefix of length i into the empty string costs i deletions. Getting those sentinels wrong is why an otherwise-correct edit-distance solution comes back off by a constant.

edit_distance.py

def min_distance(word1, word2):
    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          # delete all i characters of word1
    for j in range(n + 1):
        dp[0][j] = j          # insert all j characters of word2
 
    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]
 
 
print(min_distance("horse", "ros"))   # expect 3

>>> min_distance("horse", "ros") walks horse -> rorse -> rose -> ros: replace h with r, delete r, delete e — three operations, matching the table’s dp[5][3] = 3.

The variant map

All three recurrences are the same machine with a different combine step. Once you can name the mutation, you can write the code.

Variant	State	Combine step	Canonical problem
Longest run ending here	one index `i`	`max` over smaller predecessors	300 LIS
Align two prefixes, count matches	`(i, j)`	match → diagonal + 1; else `max` of the two neighbours	1143 LCS
Align two prefixes, count edits	`(i, j)`	match → diagonal; else `1 + min` of three neighbours	72 Edit Distance
Same, but count the ways	`(i, j)`	replace `max`/`min` with `+`	115 Distinct Subsequences · 97 Interleaving String
Same, but with wildcards	`(i, j)`	the mismatch branch splits on the pattern character	44 Wildcard · 10 Regex Matching
One sequence, fixed budget	`(i, k)`	add a second dimension for the budget	188 Best Time to Buy and Sell Stock IV

Time and space complexity

Problem	Time	Space
LIS, $O(n^2)$ table	$O(n^2)$	$O(n)$
LIS, patience sorting	$O(n \log n)$	$O(n)$
LCS	$O(mn)$	$O(mn)$ (or $O(\min(m, n))$ rolling)
Edit Distance	$O(mn)$	$O(mn)$ (or $O(\min(m, n))$ rolling)

When to use it

LIS whenever the question is about picking the longest ordered (increasing, decreasing, or non-decreasing) chain from a sequence, or is secretly LIS in disguise (e.g. “longest chain of pairs”, “box stacking”).
LCS whenever two sequences need to be compared for their longest shared ordered (not contiguous) structure — diffing tools, DNA alignment, “Longest Palindromic Subsequence” (LCS of a string with its reverse).
Edit Distance whenever the question allows insert/delete/replace operations to transform one sequence into another — spell checkers, DNA alignment with mismatches, fuzzy string matching.

Practice — real LeetCode problems

These three are the most reused DP recurrences in interviews. LIS teaches the $O(n \log n)$ escape hatch, LCS teaches the two-string grid, and Edit Distance teaches a grid where three transitions compete.

LC 300 — Longest Increasing Subsequence · Medium

Problem. Return the length of the longest strictly increasing subsequence. A subsequence keeps order but need not be contiguous.

Constraints. 1 <= len(nums) <= 2500, -10**4 <= nums[i] <= 10**4.

Examples. [10,9,2,5,3,7,101,18] gives 4 ([2,3,7,101]) · [0,1,0,3,2,3] gives 4 · [7,7,7,7] gives 1

Editorial · approach, complexity, follow-ups

Two solutions worth knowing, and an interviewer will usually want the first explained and the second coded.

$O(n^2)$ DP. dp[i] is the length of the best increasing subsequence ending at i. Look back at every j < i with nums[j] < nums[i] and take the best. The answer is max(dp). This one generalises easily — weights, counts, 2D versions — so it is the one to keep in reserve.

$O(n \log n)$ patience sorting. tails[k] is the smallest value that can end an increasing subsequence of length k + 1. It is sorted for a structural reason: a longer subsequence needs at least as large a tail. That sortedness is what licenses the binary search, and it is the step to justify out loud.

Time $O(n \log n)$ . Space $O(n)$ .

tails is not the answer sequence. Only its length is meaningful. On the given example it happens to come out as [2,3,7,18], which is a real subsequence, so the example hides the issue. [2,6,8,3,4,5,1] exposes it: tails ends as [1,3,4,5], and the 1 sits at the last index, after the 5 — not a subsequence at all. The length 4 is still correct ([2,3,4,5]). Claiming tails is the answer is a classic interview stumble.
Strictly increasing needs bisect_left. With bisect_right you would allow equal neighbours and [7,7,7,7] would answer 4 instead of 1. If the problem asked for non-decreasing, bisect_right is exactly the fix — that one-token swap is a favourite follow-up.
Every element distinct and sorted gives n; reverse-sorted gives 1. Those are the two extremes to sanity-check against.

Follow-ups you should expect: “Reconstruct the actual subsequence?” — record each element’s position in tails plus a parent index, then walk back. “Count the LIS (LC 673)?” — the $O(n^2)$ DP with a parallel count array. “Longest non-decreasing?” — bisect_right. “Russian Doll Envelopes (LC 354)?” — sort by width ascending and height descending, then LIS on heights; the descending tie-break is what forbids equal widths from stacking. “Minimum deletions to make it increasing?” — n minus the LIS.

LC 1143 — Longest Common Subsequence · Medium

Problem. Return the length of the longest subsequence common to both strings, or 0 if there is none.

Constraints. 1 <= len(text1), len(text2) <= 1000, lowercase letters.

Examples. "abcde" and "ace" gives 3 ("ace") · "abc" and "abc" gives 3 · "abc" and "def" gives 0

Editorial · approach, complexity, follow-ups

The template for two-sequence DP: one index per sequence, and the decision is which index to advance.

Time $O(mn)$ . Space $O(mn)$ , reducible to $O(\min(m, n))$ by keeping only the previous row — though then you lose the ability to reconstruct the string.

The padding row and column encode “one string is exhausted, so the LCS is 0”. Building an m by n table instead forces awkward i == 0 guards inside the loop.
text1[i-1] versus dp[i] is the off-by-one that bites everyone: dp is indexed by counts, the strings by positions.
Subsequence, not substring. "abcde" and "ace" gives 3 for the subsequence; the longest common substring is only 1. That is a different recurrence — on a mismatch you reset to 0 rather than inheriting a neighbour, and the answer is the table maximum, not the corner.
Disjoint alphabets give 0, and the whole table stays zero.
max of the two neighbours is not a greedy shortcut — it is the exhaustive choice, because if the last characters differ then at least one of them cannot be in the LCS.

Follow-ups you should expect: “Return the string itself?” — walk back from dp[m][n]: equal characters mean step diagonally and prepend, otherwise move towards the larger neighbour. “Shortest Common Supersequence (LC 1092)?” — m + n - LCS. “Minimum deletions to make the strings equal (LC 583)?” — m + n - 2 * LCS. “Longest Palindromic Subsequence (LC 516)?” — LCS of the string with its own reverse. “Delete Operation for Two Strings?” — same identity. This one recurrence is worth more than any five others in the DP section.

LC 72 — Edit Distance · Medium

Problem. Return the minimum number of insertions, deletions and replacements needed to turn word1 into word2.

Constraints. 0 <= len(word1), len(word2) <= 500, lowercase letters.

Examples. "horse" to "ros" gives 3 · "intention" to "execution" gives 5

Editorial · approach, complexity, follow-ups

Levenshtein distance — the same grid as LCS with a non-zero base and three transitions instead of two. Being able to point at a cell and name which neighbour is which operation is the difference between having understood it and having memorised it:

Neighbour	Operation	Reading
`dp[i-1][j]`	delete	drop `word1[i-1]`, keep aiming at the same target prefix
`dp[i][j-1]`	insert	add `word2[j-1]`, having already matched `word1[:i]`
`dp[i-1][j-1]`	replace	overwrite `word1[i-1]` with `word2[j-1]`

Time $O(mn)$ . Space $O(mn)$ , reducible to $O(n)$ with one rolling row — but you must stash dp[i-1][j-1] before overwriting it.

The base row and column are 0..n and 0..m, not zeros. This is the single most common bug: with a zero base, "" to "a" returns 0 instead of 1.
Empty inputs are inside the constraints here, and the base cases already cover them — no special branch.
The diagonal is free on a match, not 1 + dp[i-1][j-1]. Getting that wrong makes identical strings cost their length.
"horse" to "ros" = 3. Trace it: horse to rorse (replace h with r), to rose (delete the second r), to ros (delete e). Walking one real path builds far more confidence than re-reading the recurrence.

Follow-ups you should expect: “Print the actual operations?” — backtrack from the corner and record which neighbour you came from. “Different costs per operation?” — multiply each term by its cost; the structure is unchanged. “Only insert and delete allowed?” — drop the replace term, and the answer becomes m + n - 2 * LCS. “One Edit Distance (LC 161)?” — an $O(n)$ two-pointer scan, because a distance of at most 1 does not need a table. “Transpositions too?” — Damerau-Levenshtein, one more term. “Words of length $10^5$ ?” — $10^{10}$ cells is too many; you need Hirschberg’s algorithm for linear space, or a bounded-band DP if the distance is known to be small.

LeetCode problem set

Generated from the problem database, so every entry carries its sheet membership and reported companies. Progress is saved in this browser.

7 problems

0 easy5 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

72Edit DistancemediumLCS's cousin, with insert/delete/replaceNeetCode 150LeetCode Top Interview 150googleamazonmicrosoftbytedance
300Longest Increasing SubsequencemediumThe exact $O(n^2)$ and $O(n \log n)$ templates aboveNeetCode 150Blind 75LeetCode Top Interview 150googlemicrosoftbytedanceuber
1143Longest Common SubsequencemediumThe 2D recurrence aboveNeetCode 150googleamazonmicrosoft
516Longest Palindromic SubsequencemediumRun LCS on the string against its own reverse
583Delete Operation for Two Stringsmedium`m + n - 2 * lcs_length`, built directly on LCS
10Regular Expression MatchinghardNeetCode 150
115Distinct SubsequenceshardNeetCode 150

Pitfalls

The five ways these solutions come back wrong, in the order they actually happen:

Returning dp[-1] from LIS. dp[i] is the best run ending at i; the best run overall can end anywhere. The answer is max(dp). This passes [1,2,3] and fails [3,1,2], so samples will not catch it.
Zeroing the edges of the Edit Distance table. LCS base cases are zeros; edit distance base cases count up (dp[i][0] = i, dp[0][j] = j). Copy the LCS skeleton without changing this and every answer is short by a constant.
Off-by-one between the table and the string. The table is (m+1) × (n+1) and row i corresponds to a[i-1]. Writing a[i] inside the loop is the single most common index bug here; it silently drops the last character rather than raising.
Optimising space too early. Collapsing to one row is easy and correct for the length, but it destroys the information needed to reconstruct the actual subsequence. Keep the full table until you know which the problem wants.
Assuming strict inequality in LIS. nums[j] < nums[i] gives strictly increasing. Non-decreasing needs <=, and “strictly increasing” versus “non-decreasing” is a real distinction problems make deliberately.

Interview follow-ups

They ask	What they’re checking	The answer
“Can you do LIS faster than $O(n^2)$ ?”	Whether you know the patience-sorting variant	Yes — $O(n \log n)$ with a `tails` array and `bisect_left`. State clearly that `tails` is not itself a valid subsequence; recovering the actual sequence needs a parent array
“Reduce the space”	Whether you see the row dependency	Each row reads only the row above, so two rows — or one row plus a saved diagonal — gives $O(\min(m, n))$
“Return the subsequence, not the length”	Whether you understand the table is not the answer	Walk back from `dp[m][n]`: diagonal on a match, otherwise toward the larger neighbour. Requires the full table, so mention it before optimising space
“What if the strings are a million characters?”	Practical limits	$O(m \cdot n)$ is $10^{12}$ — infeasible. Say so. Then offer Hirschberg’s algorithm for linear-space LCS, or a diff algorithm (Myers) if the strings are mostly similar
“Minimum deletions to make two strings equal”	Whether you spot a disguised LCS	`m + n - 2 * lcs_length` — every character outside the LCS must go, from both strings (LC 583)
“Now insertions cost 2 and deletions cost 1”	Whether the recurrence is understood or memorised	Replace the uniform `1 +` with the per-operation cost in the `min`. The table shape does not change at all

Dry run

Edit Distance on "horse" -> "ros", filled by hand. Only the interesting cells are shown; note how row 0 and column 0 come from the base cases, not from the recurrence.

	ε	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

Read the three bolded cells:

dp[o][o] = 1 — 'o' == 'o', so it inherits the diagonal dp[h][r] = 1 for free. One edit so far (replacing h).
dp[r][r] = 2 — 'r' == 'r', inherits dp[o][ε] = 2.
dp[e][s] = 3 — mismatch, so 1 + min(diag 2, above 2, left 3) = 3.

The answer dp[5][3] = 3 is the well-known horse → rorse → rose → ros. Tracing back through the choices recovers exactly that edit script.

Self-check

pch.quizTag Classic sequence DP — self-check

For LIS with the O(n^2) table, what do you return?

pch.quizShowAnswer

B — max(dp) — dp[i] is the length of the best run ENDING AT i. The best run overall may end anywhere, so the answer is max(dp). Returning dp[-1] is the classic wrong answer and passes surprisingly many sample inputs.
In the LCS recurrence, why does a mismatch read TWO cells but a match reads only ONE?

pch.quizShowAnswer

B — A match consumes a character from both strings at once, so there is only one predecessor state; a mismatch must drop one character but we do not know which, so both options are tried — This is the whole shape of two-sequence DP. Match → advance both pointers → single diagonal predecessor. Mismatch → advance exactly one pointer, and since the choice is not forced, take the better of the two.
Edit Distance base cases: what is dp[i][0]?

pch.quizShowAnswer

C — i — deleting all i characters of the prefix — Turning a length-i prefix into the empty string costs i deletions, so column 0 counts up. Symmetrically dp[0][j] = j insertions. Initialising these to 0 like LCS is the most common edit-distance bug.
In the O(n log n) LIS, what does tails[k] hold?

pch.quizShowAnswer

B — The smallest possible tail value among all increasing subsequences of length k + 1 — tails is therefore sorted, which is what makes bisect_left applicable. Crucially tails is NOT itself a valid subsequence of the input — it only encodes lengths. Reconstructing the actual subsequence needs a separate parent array.
Minimum deletions to make two strings equal, given lcs_length?

pch.quizShowAnswer

B — m + n - 2 * lcs_length — Every character not in the LCS must be deleted, from BOTH strings — hence the factor of 2. This reduction (LC 583) is a common way to disguise LCS, and spotting it is worth practising.

Recall card

Cue — two sequences and a question about a common/aligned/transformed subsequence; or one sequence and “longest increasing/…-ing subsequence”.
State — a prefix, or a pair of prefixes: dp[i][j] answers the question for a[:i] and b[:j].
Recurrence shape — match → diagonal (± 1); mismatch → best of the neighbours you are allowed to move to.
Base cases — LCS: zeros. Edit distance: dp[i][0] = i, dp[0][j] = j. Getting this wrong is the usual off-by-a-constant.
Complexity — $O(m \cdot n)$ time and space; space collapses to $O(\min(m, n))$ because each row reads only the row above. LIS drops from $O(n^2)$ to $O(n \log n)$ via patience sorting.
Answer vs. table — the table holds a length. The actual subsequence or edit script comes from walking backward through the choices.

Recap

LIS, LCS, and Edit Distance all define their state over prefixes of one or two sequences.
LIS has both an $O(n^2)$ table version and an $O(n \log n)$ patience sorting version using bisect_left on a tails array.
LCS’s recurrence branches on a character match (extend the diagonal) vs. mismatch (take the better neighbor); Edit Distance adds a third option (replace) to that same shape.
The table isn’t just for the length — walking it backward reconstructs the actual subsequence or edit sequence.

Next: DP on Grids and Intervals — when the DP state is a 2D grid cell or a range [i, j] instead of a single prefix.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading