Dynamic Programming
The topic people fear most. It is only two ideas: notice you are solving the same subproblem twice, and write the answer down. We build up from a function you already understand.
By the end: Turn a slow recursion into a memoised, then tabulated, solution.
Dynamic programming has a reputation for being hard. It is not. It is two ideas:
- You are solving the same subproblem more than once.
- So write the answer down and look it up instead.
That is all. Everything else — tables, "bottom-up", state compression — is bookkeeping around those two sentences. We already did it once in lesson 11 with Fibonacci; this lesson turns it into a method.
Start where you already are
// You can take 1 or 2 steps. How many distinct ways to reach step n?
// To reach step n you came from n-1 or n-2. So ways(n) = ways(n-1) + ways(n-2).
let naiveCalls = 0;
function waysNaive(n) {
naiveCalls++;
if (n <= 2) return n;
return waysNaive(n - 1) + waysNaive(n - 2);
}
let memoCalls = 0;
function waysMemo(n, memo = new Map()) {
memoCalls++;
if (n <= 2) return n;
if (memo.has(n)) return memo.get(n);
const result = waysMemo(n - 1, memo) + waysMemo(n - 2, memo);
memo.set(n, result);
return result;
}
for (const n of [10, 20, 30]) {
naiveCalls = 0; memoCalls = 0;
const a = waysNaive(n), b = waysMemo(n);
console.log(`n=${n}: ${a} ways | naive ${naiveCalls.toLocaleString('en-US')} calls | memo ${memoCalls} calls`);
}Output
The method: five questions
Answer these in order for any DP problem and the code is mechanical. Skipping straight to the table is why people find DP hard.
- What is the state? What minimum set of values identifies a subproblem? This becomes your function parameters, or your array indices.
- What does the answer mean? Write a sentence: "
dp[i]is the maximum sum ending at indexi." Be exact about ending at versus up to; most DP bugs are here. - What is the recurrence? How does this state depend on smaller ones?
- What are the base cases? The smallest states, answered directly.
- What order do you fill it in? Every state must be computed after the states it depends on.
// PROBLEM: given house values in a row, take the maximum total without
// taking two adjacent houses.
// 1. STATE: the index i we have reached.
// 2. MEANING: dp[i] = the best total using only houses 0..i.
// 3. RECURRENCE: at house i, either skip it (dp[i-1]) or take it
// (nums[i] + dp[i-2]). Take the better.
// 4. BASE: dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]).
// 5. ORDER: left to right, since i depends on i-1 and i-2.
function maxNonAdjacent(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
console.log(' nums:', nums);
console.log(' dp: ', dp);
return dp[nums.length - 1];
}
console.log('answer:', maxNonAdjacent([2, 7, 9, 3, 1]));
console.log('answer:', maxNonAdjacent([2, 1, 1, 2]));
console.log('answer:', maxNonAdjacent([5]));Output
Top-down and bottom-up
Two ways to write the same DP. Top-down (memoisation) is recursion plus a cache; it follows the recurrence directly and only computes states it needs. Bottom-up (tabulation) is a loop filling a table in dependency order; no recursion, so no stack limit.
const coins = [1, 5, 6, 9];
// TOP-DOWN: write the recurrence, add a cache.
function minCoinsTopDown(amount, memo = new Map()) {
if (amount === 0) return 0;
if (amount < 0) return Infinity;
if (memo.has(amount)) return memo.get(amount);
let best = Infinity;
for (const coin of coins) {
const rest = minCoinsTopDown(amount - coin, memo);
if (rest + 1 < best) best = rest + 1;
}
memo.set(amount, best);
return best;
}
// BOTTOM-UP: fill a table from 0 upwards.
function minCoinsBottomUp(amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // zero coins make zero
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) dp[a] = dp[a - coin] + 1;
}
}
return dp[amount];
}
for (const amount of [11, 12, 0, 3]) {
const t = minCoinsTopDown(amount), b = minCoinsBottomUp(amount);
console.log(`amount ${String(amount).padStart(2)}: top-down ${t}, bottom-up ${b}, agree: ${t === b}`);
}
// The greedy answer is wrong here, which is why this needs DP.
function greedy(amount) {
let left = amount, count = 0;
for (const c of [...coins].sort((a, b) => b - a)) { while (left >= c) { left -= c; count++; } }
return left === 0 ? count : Infinity;
}
console.log('for 11, greedy gives', greedy(11), 'but the real answer is', minCoinsBottomUp(11), '(5+6)');Output
Space compression
Once bottom-up works, look at how far back the recurrence reaches. If dp[i] only needs dp[i-1] and dp[i-2], you do not need the whole array — two variables will do. That takes O(n) space to O(1).
function maxNonAdjacentArray(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length + 1).fill(0);
dp[1] = nums[0];
for (let i = 2; i <= nums.length; i++) dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
return dp[nums.length];
}
function maxNonAdjacentCompressed(nums) {
let skip = 0; // best if we do not take the previous house
let take = 0; // best overall so far
for (const value of nums) {
const next = Math.max(take, skip + value);
skip = take;
take = next;
}
return take;
}
for (const input of [[2, 7, 9, 3, 1], [2, 1, 1, 2], [5], []]) {
console.log(JSON.stringify(input).padEnd(16),
'array:', maxNonAdjacentArray(input),
'| O(1) space:', maxNonAdjacentCompressed(input));
}Output
The one-dimensional patterns
// dp[i] = the best sum of a subarray ENDING at i. Either extend the previous
// best, or start fresh at i. That definition is the whole insight.
function maxSubarray(nums) {
let best = nums[0];
let endingHere = nums[0];
const trace = [];
for (let i = 1; i < nums.length; i++) {
endingHere = Math.max(nums[i], endingHere + nums[i]); // extend or restart
best = Math.max(best, endingHere);
trace.push(`i=${i} value=${nums[i]} endingHere=${endingHere} best=${best}`);
}
return { best, trace };
}
const r = maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
console.log('best subarray sum:', r.best);
r.trace.forEach(t => console.log(' ' + t));
console.log('all negative:', maxSubarray([-3, -1, -2]).best);Output
// O(n^2): dp[i] = the length of the longest increasing subsequence ending at i.
function lisQuadratic(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++)
for (let j = 0; j < i; j++)
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
return Math.max(...dp);
}
// O(n log n): keep `tails`, where tails[k] is the smallest possible tail of an
// increasing subsequence of length k+1. Binary search for where each value goes.
function lisFast(nums) {
const tails = [];
for (const x of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) { // lowerBound: first tail >= x
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
tails[lo] = x; // replace, or append if lo === length
}
return tails.length;
}
for (const input of [[10,9,2,5,3,7,101,18], [0,1,0,3,2,3], [7,7,7,7], []]) {
console.log(JSON.stringify(input).padEnd(26),
'O(n^2):', lisQuadratic(input), '| O(n log n):', lisFast(input));
}Output
Two dimensions
When there are two independent things varying — two strings, or items and capacity — the state needs two indices. The table becomes a grid, and the recurrence usually looks at the neighbours above, left, and diagonally up-left.
function lcs(a, b) {
const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
// dp[i][j] = the LCS length of a's first i characters and b's first j.
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] = dp[i - 1][j - 1] + 1; // match: use both
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // drop one
}
}
console.log(' ' + ['-', ...b].map(c => c.padStart(3)).join(''));
dp.forEach((row, i) => console.log(
(i === 0 ? '-' : a[i - 1]).padStart(3) + ' ' + row.map(v => String(v).padStart(3)).join('')
));
return dp[a.length][b.length];
}
console.log('LCS length:', lcs('abcde', 'ace'));Output
function editDistance(a, b) {
const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
// Base: turning a prefix into the empty string costs one delete per character.
for (let i = 0; i <= a.length; i++) dp[i][0] = i;
for (let j = 0; j <= b.length; j++) dp[0][j] = j;
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] = dp[i - 1][j - 1]; // free: characters match
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // delete from a
dp[i][j - 1], // insert into a
dp[i - 1][j - 1] // replace
);
}
}
}
return dp[a.length][b.length];
}
console.log("horse → ros:", editDistance('horse', 'ros')); // 3
console.log("intention → execution:", editDistance('intention', 'execution')); // 5
console.log("same:", editDistance('abc', 'abc')); // 0
console.log("empty:", editDistance('', 'abc')); // 3Output
// Count paths from top-left to bottom-right moving only right or down.
function uniquePaths(rows, cols) {
const dp = Array.from({ length: rows }, () => new Array(cols).fill(1));
for (let r = 1; r < rows; r++)
for (let c = 1; c < cols; c++)
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // from above plus from the left
return dp[rows - 1][cols - 1];
}
// With obstacles, and compressed to a single row.
function uniquePathsWithObstacles(grid) {
const rows = grid.length, cols = grid[0].length;
if (grid[0][0] === 1) return 0;
const dp = new Array(cols).fill(0);
dp[0] = 1;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 1) dp[c] = 0; // blocked: no paths through
else if (c > 0) dp[c] += dp[c - 1]; // dp[c] already holds the row above
}
}
return dp[cols - 1];
}
console.log('3x7 grid:', uniquePaths(3, 7)); // 28
console.log('1x1 grid:', uniquePaths(1, 1)); // 1
console.log('with an obstacle:', uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])); // 2
console.log('start blocked:', uniquePathsWithObstacles([[1,0],[0,0]])); // 0Output
The knapsack family
A large group of problems reduces to: given items with values, choose some subset subject to a limit. Recognising a problem as knapsack tells you the state immediately.
function knapsack(weights, values, capacity) {
const n = weights.length;
// dp[c] = the best value achievable with capacity exactly c or less.
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
// BACKWARDS, so each item is used at most once: dp[c - w] must still refer
// to a state that has not yet considered item i.
for (let c = capacity; c >= weights[i]; c--) {
dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
}
}
return dp[capacity];
}
console.log('best value:', knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9
console.log('capacity 0:', knapsack([1, 2], [10, 20], 0)); // 0
// Unbounded knapsack: items reusable. The ONLY change is loop direction.
function knapsackUnbounded(weights, values, capacity) {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let c = weights[i]; c <= capacity; c++) { // FORWARDS: reuse allowed
dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
}
}
return dp[capacity];
}
console.log('unbounded:', knapsackUnbounded([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 10Output
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false; // odd total cannot split evenly
const target = total / 2;
// Can we hit exactly `target` using a subset? A 0/1 knapsack on booleans.
const reachable = new Array(target + 1).fill(false);
reachable[0] = true;
for (const x of nums) {
for (let sum = target; sum >= x; sum--) { // backwards: each number once
if (reachable[sum - x]) reachable[sum] = true;
}
}
return reachable[target];
}
console.log([1, 5, 11, 5], '→', canPartition([1, 5, 11, 5])); // true, 11 = 1+5+5
console.log([1, 2, 3, 5], '→', canPartition([1, 2, 3, 5])); // false
console.log([1, 1], '→', canPartition([1, 1])); // trueOutput
// The loop ORDER decides whether order matters. Coins outside means
// combinations; amounts outside would count permutations.
function countCombinations(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) { // coins in the OUTER loop
for (let a = coin; a <= amount; a++) dp[a] += dp[a - coin];
}
return dp[amount];
}
function countPermutations(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let a = 1; a <= amount; a++) { // amount in the OUTER loop
for (const coin of coins) if (coin <= a) dp[a] += dp[a - coin];
}
return dp[amount];
}
console.log('ways to make 5 from [1,2,5], order ignored:', countCombinations([1, 2, 5], 5)); // 4
console.log('ways to make 5 from [1,2,5], order counts: ', countPermutations([1, 2, 5], 5)); // 9
console.log('ways to make 4 from [1,2,3], order ignored:', countCombinations([1, 2, 3], 4)); // 4Output
Reconstructing the answer, not just its value
function knapsackWithItems(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let c = 0; c <= capacity; c++) {
dp[i][c] = dp[i - 1][c]; // skip item i-1
if (weights[i - 1] <= c) {
dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - weights[i - 1]] + values[i - 1]);
}
}
}
// Walk the table backwards: if the value changed, item i-1 was taken.
const chosen = [];
let c = capacity;
for (let i = n; i > 0; i--) {
if (dp[i][c] !== dp[i - 1][c]) {
chosen.push(i - 1);
c -= weights[i - 1];
}
}
return { best: dp[n][capacity], items: chosen.reverse() };
}
console.log(knapsackWithItems([1, 3, 4, 5], [1, 4, 5, 7], 7));Output
Recognising DP
Signals, in rough order of reliability:
- The question asks for a maximum, minimum, count of ways, or is it possible — rather than for a list of answers.
- You can describe the answer in terms of the answer to a slightly smaller version.
- A backtracking solution exists but recomputes the same states.
- Choices at each step, where a greedy choice is provably wrong.
- Two sequences being compared, or a grid being traversed with restricted moves.
And the anti-signal: if the question asks you to list every arrangement, it is backtracking, not DP. The output is exponential so no table can help.
function wordBreak(s, dictionary) {
const words = new Set(dictionary);
// dp[i] = can s.slice(0, i) be split entirely into dictionary words?
const dp = new Array(s.length + 1).fill(false);
dp[0] = true; // the empty prefix is fine
for (let end = 1; end <= s.length; end++) {
for (let start = 0; start < end; start++) {
if (dp[start] && words.has(s.slice(start, end))) { dp[end] = true; break; }
}
}
return dp[s.length];
}
console.log('leetcode / [leet, code]:', wordBreak('leetcode', ['leet', 'code']));
console.log('applepenapple:', wordBreak('applepenapple', ['apple', 'pen']));
console.log('catsandog:', wordBreak('catsandog', ['cats','dog','sand','and','cat']));Output
Your turn: six DP problems
For each, write the state and its meaning as a comment before the code.
minCostClimbing(cost)— paycost[i]to step off stairi, taking 1 or 2 steps, starting from index 0 or 1. Minimum total to get past the top.lengthOfLIS(nums)— you saw both versions above; write theO(n log n)one from memory.numDecodings(s)— how many ways to decode a digit string where 1 to 26 map to A to Z. Watch the zeroes.longestPalindromicSubstring(s)— expand around each of the2n-1centres, which isO(n²)time andO(1)space and beats the DP table.maxProduct(nums)— maximum product subarray. Track the running max and min, because a negative flips them.longestCommonSubsequence(a, b)— return the actual subsequence string, not just its length.
Output
Recap
- DP is two ideas: you are recomputing the same subproblem, so store the answer. Nothing more.
- Answer five questions before coding — state, its exact meaning, recurrence, base cases, fill order — and the code follows.
- Write top-down memoisation first because it mirrors the recurrence; then offer bottom-up to remove recursion depth and compress space.
- "Ending at
i" is the definition that makes most subarray problems local and easy. - In knapsack, looping capacity backwards means each item once and forwards means reuse; and coins-outer counts combinations while amount-outer counts permutations.