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_leftbisect_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.

Longest Increasing Subsequence

Define dp[i]dp[i] as the length of the longest increasing subsequence that ends exactly at index ii. To extend a subsequence ending at some earlier index jj up to ii, you need nums[j] < nums[i]nums[j] < nums[i] — so dp[i]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)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])

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])

That’s $O(n^2)$ — fine up to a few thousand elements, but too slow once nn 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 tailstails where tails[k]tails[k] is the smallest possible tail value among all increasing subsequences of length k + 1k + 1 found so far. tailstails is always sorted, which means you can binary search it: for each new number xx, find the leftmost slot where xx could sit (bisect_leftbisect_left), and either extend tailstails (if xx 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

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 text1text1 and text2text2? The state is a pair of prefix lengths (i, j)(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")

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")

Delete Operation for Two Strings is LCS in disguise: the minimum number of deletions to make two strings equal is m + n - 2 * lcs_lengthm + 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 minmin 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]dp[i-1][j] deletes a character from word1word1, dp[i][j-1]dp[i][j-1] inserts a character to match word2word2, and dp[i-1][j-1]dp[i-1][j-1] replaces one character for another.

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

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")>>> min_distance("horse", "ros") walks horse -> rorse -> rose -> roshorse -> rorse -> rose -> ros: replace hh with rr, delete rr, delete ee — three operations, matching the table’s dp[5][3] = 3dp[5][3] = 3.

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) <= 25001 <= len(nums) <= 2500, -10**4 <= nums[i] <= 10**4-10**4 <= nums[i] <= 10**4.

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

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]dp[i] is the length of the best increasing subsequence ending at ii. Look back at every j < ij < i with nums[j] < nums[i]nums[j] < nums[i] and take the best. The answer is max(dp)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]tails[k] is the smallest value that can end an increasing subsequence of length k + 1k + 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)$ .

tailstails is not the answer sequence. Only its length is meaningful. On the given example it happens to come out as [2,3,7,18][2,3,7,18], which is a real subsequence, so the example hides the issue. [2,6,8,3,4,5,1][2,6,8,3,4,5,1] exposes it: tailstails ends as [1,3,4,5][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][2,3,4,5]). Claiming tailstails is the answer is a classic interview stumble.
Strictly increasing needs bisect_leftbisect_left. With bisect_rightbisect_right you would allow equal neighbours and [7,7,7,7][7,7,7,7] would answer 4 instead of 1. If the problem asked for non-decreasing, bisect_rightbisect_right is exactly the fix — that one-token swap is a favourite follow-up.
Every element distinct and sorted gives nn; 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 tailstails 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_rightbisect_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?” — nn 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) <= 10001 <= len(text1), len(text2) <= 1000, lowercase letters.

Examples. "abcde""abcde" and "ace""ace" gives 33 ("ace""ace") · "abc""abc" and "abc""abc" gives 33 · "abc""abc" and "def""def" gives 00

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 mm by nn table instead forces awkward i == 0i == 0 guards inside the loop.
text1[i-1]text1[i-1] versus dp[i]dp[i] is the off-by-one that bites everyone: dpdp is indexed by counts, the strings by positions.
Subsequence, not substring. "abcde""abcde" and "ace""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.
maxmax 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]dp[m][n]: equal characters mean step diagonally and prepend, otherwise move towards the larger neighbour. “Shortest Common Supersequence (LC 1092)?” — m + n - LCSm + n - LCS. “Minimum deletions to make the strings equal (LC 583)?” — m + n - 2 * LCSm + 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 word1word1 into word2word2.

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

Examples. "horse""horse" to "ros""ros" gives 33 · "intention""intention" to "execution""execution" gives 55

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]dp[i-1][j]`	delete	drop `word1[i-1]word1[i-1]`, keep aiming at the same target prefix
`dp[i][j-1]dp[i][j-1]`	insert	add `word2[j-1]word2[j-1]`, having already matched `word1[:i]word1[:i]`
`dp[i-1][j-1]dp[i-1][j-1]`	replace	overwrite `word1[i-1]word1[i-1]` with `word2[j-1]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]dp[i-1][j-1] before overwriting it.

The base row and column are 0..n0..n and 0..m0..m, not zeros. This is the single most common bug: with a zero base, """" to "a""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]1 + dp[i-1][j-1]. Getting that wrong makes identical strings cost their length.
"horse""horse" to "ros""ros" = 3. Trace it: horsehorse to rorserorse (replace hh with rr), to roserose (delete the second rr), to rosros (delete ee). 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 * LCSm + 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

#	Problem	Difficulty	The twist
300	Longest Increasing Subsequence	Medium	The exact $O(n^2)$ and $O(n \log n)$ templates above
1143	Longest Common Subsequence	Medium	The 2D recurrence above
72	Edit Distance	Medium	LCS’s cousin, with insert/delete/replace
583	Delete Operation for Two Strings	Medium	`m + n - 2 * lcs_lengthm + n - 2 * lcs_length`, built directly on LCS
516	Longest Palindromic Subsequence	Medium	Run LCS on the string against its own reverse

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_leftbisect_left on a tailstails 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][i, j] instead of a single prefix.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Classic DP: LIS, LCS, and Edit Distance

What you’ll learn

Longest Increasing Subsequence

The O(n log n) trick: patience sorting

Longest Common Subsequence

Edit Distance (Levenshtein distance)

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 300 — Longest Increasing Subsequence · Medium

LC 1143 — Longest Common Subsequence · Medium

LC 72 — Edit Distance · Medium

LeetCode problem set

Recap

Was this page helpful?