2D DP: Knapsack and Common Subsequences

0/1 knapsack

A bag can carry at most W kg. Each item has a weight and a value, and you either take it or leave it. What's the most value you can carry?

State: dp[i][w] = best value using the first i items with capacity w. Transition: skip item i (dp[i − 1][w]) or take it if it fits (dp[i − 1][w − weight] + value).

def knapsack(items, W):
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                       # skip
            if weight <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)   # take
    return dp[n][W]

items = [(1, 1), (3, 4), (4, 5), (5, 7)]     # (weight, value)
print(knapsack(items, 7))

Output

9

Think of it like this: Packing for a trip with a 7 kg limit: a 3 kg camera (value 4) plus a 4 kg laptop (value 5) beats one 5 kg item worth 7 plus a 1 kg item worth 1.

Longest common subsequence (LCS)

A subsequence keeps letters in order but may skip some: “ace” is a subsequence of “abcde”. The LCS of two words is the longest one they share. dp[i][j] = LCS length of the first i letters of a and first j letters of b:

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1         # letters match: extend
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop a letter from one word
    return dp[len(a)][len(b)]

print(lcs("abcde", "ace"))
print(lcs("AGGTAB", "GXTXAYB"))

Output

3
4

Both tables have (n + 1) × (m + 1) cells, each filled in O(1): O(n × m) time. Tools like git diff use this idea to compare files.

Common mistake: Off-by-one errors are the most common DP bug. Using an extra row and column for “zero items / empty word” keeps the indexes simple.