Quick Overview
At every item you face one binary choice: take it or leave it. Dynamic programming caches the best value for each remaining capacity, so `dp[i][c]` is computed once instead of re-derived down every branch.
Given N items where each item has a weight and a value, determine the maximum value you can carry in a knapsack of maximum weight capacity W.
For item i with weight w and value v at capacity c:
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)
function knapsack01(weights, values, capacity) {
const n = weights.length;
// 1D Array Space Optimization (Iterate backwards to prevent reusing same item!)
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
const w = weights[i];
const v = values[i];
// Must iterate backwards from capacity down to w!
for (let c = capacity; c >= w; c--) {
dp[c] = Math.max(dp[c], dp[c - w] + v);
}
}
return dp[capacity];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack01(weights, values, 5)); // Output: 7 (Items with weights 2 and 3)
Find the fewest coins needed to make up a given target amount (infinite coin reuse):
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // Base case: 0 amount requires 0 coins
for (const coin of coins) {
// Iterate forward because coins can be reused!
for (let a = coin; a <= amount; a++) {
dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 2, 5], 11)); // Output: 3 (5 + 5 + 1)
c = capacity down to w).c = w up to capacity).Use knapsack patterns for subset partition problems. Next, let's explore Longest Common Subsequence (LCS)!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.