Day 64: Dynamic Programming: Common Patterns (Knapsack, Subsequences)
Recognize the handful of DP "shapes" that cover most interview DP questions — 0/1 knapsack, unbounded knapsack, and longest common subsequence.
Study
Concepts
0/1 Knapsack: include-or-exclude each item, once
The 0/1 Knapsack shape applies whenever you choose a subset of items (each usable AT MOST ONCE) to maximize/minimize some value under a capacity constraint — "Subset Sum", "Partition Equal Subset Sum", and "Target Sum" are all 0/1 Knapsack in disguise. The recurrence at each item asks exactly two questions: what is the best result if I EXCLUDE this item, and what is the best result if I INCLUDE it (only valid if it fits the remaining capacity) — take the better of the two.
Unbounded Knapsack relaxes "at most once" to "as many times as you like" (Coin Change, Rod Cutting) — the recurrence changes subtly: after including an item, you can still choose that SAME item again, which changes which cell of the table you reference next.
Longest Common Subsequence: the template for string-pair DP
LCS compares two strings via a 2D table where `dp[i][j]` = the LCS length of the first `i` characters of string A and the first `j` characters of string B. If the characters match, `dp[i][j] = 1 + dp[i-1][j-1]` (extend the diagonal); if they don't, `dp[i][j] = max(dp[i-1][j], dp[i][j-1])` (best of dropping a character from either string). This exact table shape (with minor recurrence tweaks) also solves Edit Distance, Longest Common Substring, and Shortest Common Supersequence — recognizing "two strings, comparing prefixes" as this family is a major interview time-saver.
See It
Visualizations
Visualization
LCS table for "ABCBDAB" vs "BDCAB" (partial)
Diagonal +1 on a match; otherwise carry the max of the cell above or to the left.
Build It
Code Examples
0/1 Knapsack — Partition Equal Subset Sum
// Can 'nums' be split into two subsets with equal sum?
// Reframe as: does a subset exist summing to totalSum / 2? (classic 0/1 knapsack)
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true; // sum of 0 is always achievable (the empty subset)
for (const num of nums) {
// Iterate DOWNWARD so each number is only used once (0/1, not unbounded)
for (let sum = target; sum >= num; sum--) {
dp[sum] = dp[sum] || dp[sum - num];
}
}
return dp[target];
}
console.log(canPartition([1, 5, 11, 5])); // true -> [1,5,5] and [11]Longest Common Subsequence
function longestCommonSubsequence(a, b) {
const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1]; // extend the diagonal on a match
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // best of dropping either char
}
}
}
return dp[a.length][b.length];
}
console.log(longestCommonSubsequence('ABCBDAB', 'BDCAB')); // 4 ("BCAB" or "BDAB")Remember
Key Takeaways
- 0/1 Knapsack: each item used at most once — iterate the capacity loop DOWNWARD to enforce that with a 1D table.
- Unbounded Knapsack: items reusable — iterate the capacity loop UPWARD, allowing the same item to be picked again.
- LCS-shaped DP (two strings, comparing prefixes) also underlies Edit Distance and Shortest Common Supersequence — same table, different recurrence.
- Recognize the SHAPE first (subset-sum-like? two-string-comparison-like?) before writing any code — it tells you the recurrence and table dimensions.
- A 1D rolling array replaces a 2D knapsack table once you notice each row only depends on the row directly above it.
Do It
Practice
- 1Solve "Coin Change" (minimum coins to make an amount, unbounded reuse) and explicitly identify why the capacity loop direction differs from 0/1 Knapsack.
- 2Solve "Edit Distance" by adapting the LCS table's recurrence to insert/delete/replace operations.
- 3Given a new, unfamiliar DP problem, write one paragraph identifying which of the two shapes (knapsack-like or LCS-like) it resembles and why, before attempting code.