Dynamic Programming on Sequences — Algorithms Course

What you'll learn

Comparing and transforming sequences is one of DP's biggest wins — it powers file diffs, spell-checkers, and DNA alignment. All three problems here share a two-dimensional table indexed by positions in the two sequences.

By the end you'll be able to:

Compute the longest common subsequence
Compute edit distance between two strings
Find the longest increasing subsequence, even in O(n log n)

Longest common subsequence

The LCS of two strings is the longest sequence appearing in both (not necessarily contiguously). The state dp[i][j] is the LCS length of the first i and first j characters. When the current characters match, extend the diagonal; otherwise take the best of dropping one character from either string:

LCS of AXBYC and ABC

Longest common subsequence

match → diag+1 · else → max(up, left)

computing depends on answer

1/17LCS of "AXBYC" and "ABC". The empty-prefix row and column are all 0.

Match → diagonal + 1; mismatch → max(up, left). The bottom-right cell is the answer.

LCS in code

Language

lcs.py

def lcs(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1        # match: diagonal + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # up or left
    return dp[n][m]

Tip

To recover the actual subsequence (not just its length), trace back from dp[n][m]: step diagonally on matches, otherwise toward the larger neighbor. This traceback trick works for almost every DP.

Edit distance

The edit (Levenshtein) distance is the fewest single-character insertions, deletions, or replacements to turn one string into another. Same 2-D grid, but now each mismatch takes 1 + the best of three neighbors — delete (up), insert (left), or replace (diagonal):

Language

edit_distance.py

def edit_distance(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = i     # delete all
    for j in range(m + 1): dp[0][j] = j     # insert all
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]              # no edit
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],         # delete
                                   dp[i][j - 1],         # insert
                                   dp[i - 1][j - 1])     # replace
    return dp[n][m]

Longest increasing subsequence

The LIS is the longest strictly increasing subsequence of a sequence. The simple DP is O(n²): dp[i] = 1 + the best dp[j] over earlier j with a[j] < a[i]. A slicker method keeps the smallest possible tail for each length in a sorted array and binary-searches each new element into place — O(n log n), combining DP with Module 6's binary search.

Key idea

Sequence DP almost always lives on a 2-D grid indexed by the two positions. Learn to read the three moves — diagonal (both advance), up, and left — and most string-DP problems become variations on a theme.

Recap & quick check

Key takeaways

LCS: match → diagonal + 1, else max(up, left).
Edit distance: match → diagonal, else 1 + min(delete, insert, replace).
Both live on a 2-D grid indexed by positions in the two strings.
Trace back from the last cell to recover the actual sequence or edits.
LIS is O(n²) by simple DP, or O(n log n) with a binary-searched tails array.

Quick check

1. In LCS, what happens when the two current characters match?

2. Edit distance allows which operations?

3. How do you recover the actual LCS, not just its length?

4. The fast LIS algorithm achieves which complexity?

Two more DP shapes remain: grids and intervals. Next up: Module 19 — DP on Grids & Intervals.