Dynamic Programming Patterns II: Knapsack, LCS, Edit Distance
Beyond simple memoization, there are classic DP problem families where recognizing the pattern immediately gives you the solution structure. Master these families and you will solve most DP interview problems.
Pattern 1: 0/1 Knapsack
Each item is either included or excluded. dp[i][w] = max value using items 0..i with capacity w.
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(capacity+1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])
return dp[n][capacity]
# Space-optimized 1D: iterate w backwards to prevent reuse
def knapsack_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
for j in range(capacity, w-1, -1):
dp[j] = max(dp[j], dp[j-w] + v)
return dp[capacity]
# Partition Equal Subset Sum
def can_partition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = {0}
for num in nums:
dp = dp | {s + num for s in dp}
return target in dp
Pattern 2: Unbounded Knapsack
Items can be reused unlimited times. Iterate weight forwards (not backwards).
def coin_change(coins, amount):
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for coin in coins:
for j in range(coin, amount + 1): # forwards = reuse allowed
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
def coin_change_ways(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[amount]
Pattern 3: Longest Common Subsequence (LCS)
def lcs(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[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]
# LIS in O(n log n) via patience sort
from bisect import bisect_left
def lis(nums):
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
Pattern 4: Edit Distance
def edit_distance(w1, w2):
m, n = len(w1), len(w2)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev = dp[0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if w1[i-1] == w2[j-1]:
dp[j] = prev
else:
dp[j] = 1 + min(prev, dp[j], dp[j-1])
prev = temp
return dp[n]
Pattern 5: State Machine DP (Stock Trading)
# Best Time to Buy and Sell Stock with Cooldown
def max_profit_cooldown(prices):
hold = float("-inf") # holding stock
sold = 0 # just sold (cooldown)
rest = 0 # not holding, free to buy
for price in prices:
prev_sold = sold
sold = hold + price
hold = max(hold, rest - price)
rest = max(rest, prev_sold)
return max(sold, rest)
DP Problem Classification
| Pattern | Key Decision | Canonical Problems |
|---|---|---|
| 0/1 Knapsack | Take or skip each item | Partition Sum, Target Sum, Subset Sum |
| Unbounded Knapsack | Use item 0..N times | Coin Change, Ribbon Cut, Rod Cutting |
| LCS | Match or skip chars from two strings | LCS, Edit Distance, Shortest Supersequence |
| LIS | Include or skip each element | LIS, Max Envelopes, Russian Doll |
| State Machine | Transitions between states | Stock Buy/Sell variants, Wildcard Match |
| Interval DP | Split interval [i,j] at position k | Burst Balloons, Matrix Chain, Palindrome Partition |