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 |
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the key difference between 0/1 knapsack and unbounded knapsack?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “In 0/1 knapsack, each item can only be used once — iterate the capacity array backwards to prevent an item from being counted multiple times in the same solution. In unbounded knapsack, items can be reused unlimited times — iterate the capacity array forwards so each item can contribute multiple times. This single difference (backwards vs. forwards loop) distinguishes the two patterns. Examples: 0/1 knapsack for subset sum and partition; unbounded for coin change and rod cutting.” }
},
{
“@type”: “Question”,
“name”: “How do you find the Longest Increasing Subsequence in O(n log n)?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each number, use binary search (bisect_left) to find where it fits in tails: if it is larger than all elements, extend tails (LIS gets longer); otherwise replace tails[pos] to allow for a potentially better smaller tail. The length of tails at the end is the LIS length. Time O(n log n), space O(n). Note: tails is not the actual LIS — it is a helper structure for length computation.” }
},
{
“@type”: “Question”,
“name”: “How does the state machine DP approach work for stock trading problems?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Model the problem as a finite state machine where each state captures your portfolio position. For "Buy and Sell with Cooldown": three states — hold (currently own stock), sold (just sold, on cooldown), rest (free to buy). Transitions: sold = hold + price (sell today); hold = max(hold, rest – price) (buy from rest state); rest = max(rest, prev_sold) (cooldown passes). Update all states in one pass through prices. This generalizes to any number of transactions and constraints by adding more states.” }
}
]
}