21. Advanced DP

The four DP patterns you must memorize: longest common subsequence, longest increasing subsequence, 0/1 knapsack, and matrix chain multiplication.

LCSLISknapsack

Duration

⏱ ~1.5 hours

Level

📊 Advanced

Prerequisite

🎯 Lecture 20

OUTCOME

Recognize and solve the four canonical DP patterns by reflex.

What you'll learn

1Code LCS (longest common subsequence)
2Code LIS in O(n log n) using bisect
3Solve 0/1 knapsack
4Solve matrix chain multiplication

Overview

These four patterns recur across hundreds of problems. Memorize the recurrence; the rest is just bookkeeping.

Core Concepts

1. Longest Common Subsequence (LCS)

python

def lcs(A, B):
    n, m = len(A), len(B)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i-1] == B[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[n][m]

Time/space O(nm).

2. Longest Increasing Subsequence (LIS)

python

# O(n²) — simple DP
def lis_n2(a):
    n = len(a)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) — bisect on the tail
from bisect import bisect_left
def lis_nlogn(a):
    tail = []
    for x in a:
        i = bisect_left(tail, x)
        if i == len(tail):
            tail.append(x)
        else:
            tail[i] = x
    return len(tail)
# Note: `tail` is NOT the actual LIS, but its length is correct.

3. 0/1 Knapsack

python

def knapsack(items, capacity):
    """items: list of (weight, value)"""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = items[i-1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i-1][c]
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    return dp[n][capacity]

# Space-optimized (1D):
def knapsack_1d(items, capacity):
    dp = [0] * (capacity + 1)
    for w, v in items:
        for c in range(capacity, w - 1, -1):   # reverse order!
            dp[c] = max(dp[c], dp[c-w] + v)
    return dp[capacity]

⚠️

0/1 knapsack 1D requires REVERSE iteration over capacity to avoid using the same item twice.

4. Matrix chain multiplication

python

def matrix_chain(p):
    """p: dimensions array; matrix i has dim p[i-1] × p[i]."""
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            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] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

Examples

Example 1 — src/01_lcs.py

LCS + path reconstruction to print the actual subsequence.

Example 2 — src/02_lis.py

Both O(n²) and O(n log n) LIS implementations.

Example 3 — src/03_knapsack.py

0/1 knapsack 2D and 1D versions.

Example 4 — src/04_matrix_chain.py

Matrix chain multiplication with O(n³) interval DP.

Common Mistakes

Knapsack 1D in forward order → uses item multiple times.
Confusing LIS with longest non-decreasing — use bisect_left vs bisect_right.
Trying to apply 0/1 knapsack to unbounded version (can take items multiple times) — different recurrence.
Off-by-one in interval DP — boundaries are tricky.

Recap

LCS / LIS / Knapsack / Matrix chain — the four DP that come up constantly.
Knapsack 1D needs reverse iteration.
LIS in O(n log n) uses bisect on the tail array.

Try It

BOJ 9251 (LCS).
BOJ 11053 (LIS).
BOJ 12865 (Ordinary backpack).

Example code / lecture materials

All lecture materials and example code are openly available on GitHub.

View on GitHub ↗