JS-201 · Lesson 11 of 12 · 21 min
Dynamic programming
▶ Video coming soon A video version of this lesson is on the way.
Some problems ask for the best of an enormous number of possibilities. Which donated items should go in the last van so that it carries as many meals as possible? What is the fewest number of containers that holds exactly the soup Rosa has made? How many changes turn one spelling of a family's name into another? Trying every possibility is exponential, as Lesson 6 showed with every possible group. At the eleventh session, on Tuesday, October 12, Gareth introduces the technique that makes many of these problems fast: dynamic programming.
The name is historical and slightly misleading. Richard Bellman chose it in the 1950s, partly because it sounded impressive; "programming" meant planning, as in a television program schedule, not writing code. The idea itself is simple: solve each small subproblem once, remember the answer, and build the answers to bigger subproblems from the smaller ones.
When dynamic programming applies
Two properties make a problem suitable. It has optimal substructure: the best answer to the whole problem can be built from the best answers to smaller versions of it. And it has overlapping subproblems: a straightforward recursive solution would solve the same smaller problems again and again, as naive Fibonacci did. When both hold, storing each subproblem's answer turns an exponential algorithm into a polynomial one.
There are two ways to store the answers. Memoization, from Lesson 6, keeps the recursive code and adds a cache: top-down. Tabulation fills a table of answers from the smallest subproblem upwards in a loop: bottom-up. Both do the same work. Tabulation avoids deep recursion and often lets you keep only the last few rows of the table, while memoization only computes the subproblems that are actually needed.
function fibTable(n) {
const f = [0, 1];
for (let i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
return f[n];
}
function fibTwoVars(n) {
let a = 0, b = 1; // f(i) and f(i + 1)
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
console.log(fibTable(10), fibTable(50), fibTwoVars(50), fibTwoVars(78));55 12586269025 12586269025 8944394323791464
What this code does
fibTable fills an array from f(0) and f(1) upwards, so each value is computed once from the two before it, which is O(n). fibTwoVars notices that only the last two values are ever needed and keeps just those, cutting the memory to O(1). Both give exact answers up to f(78), the largest Fibonacci number that a JavaScript number holds exactly.
Counting the ways
Many dynamic programming problems count possibilities. The youth garden has a bed 8 feet long to plant with seedlings in trays that cover either 1 foot or 2 feet of its length. How many different arrangements fill the bed exactly? The last tray is either a short one, after an arrangement for 7 feet, or a long one, after an arrangement for 6 feet. So ways(n) = ways(n − 1) + ways(n − 2), with one way to fill a length of 0 and one way to fill a length of 1. That is the Fibonacci recurrence again, which is why it turns up so often.
A similar question for the lunch counter has more choices: in how many different ways can a customer pay a given amount exactly in coins? The count must not treat the same coins in a different order as a new way. The standard trick is to consider the coin types one at a time: for each coin type, every amount can be made either without any of that coin, or with at least one, which leaves the amount minus that coin to make with the same coin types.
function waysToPay(amount, coins) {
const ways = new Array(amount + 1).fill(0);
ways[0] = 1; // one way to pay nothing: no coins
for (const c of coins) {
for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
}
return ways[amount];
}
const coins = [1, 5, 10, 25, 100]; // cents: penny, nickel, dime, quarter, dollar coin
console.log('ways to pay 25 cents:', waysToPay(25, coins));
console.log('ways to pay 1.00:', waysToPay(100, coins));
console.log('ways to pay 5.00:', waysToPay(500, coins));ways to pay 25 cents: 13 ways to pay 1.00: 243 ways to pay 5.00: 35221
What this code does
waysToPay keeps a table of how many ways each amount can be paid with the coins considered so far. Adding a coin type lets every amount reuse the count for that amount minus the coin, and taking the coin types in a fixed order means each combination is counted once, whatever order the coins are handed over in. The table has one entry per amount, so the work is the number of amounts times the number of coin types.
Fewest pieces: when greedy fails
A related question asks for the fewest coins that make an amount. The obvious method is greedy: always take the largest coin that fits. For the coins people actually use in Canada and the United States, greedy always gives the fewest coins, because those coin systems were designed that way. But greedy is not correct in general. Rosa's kitchen has soup containers of 1, 3 and 4 quarts, and she wants to hold exactly 6 quarts in as few containers as possible. Greedy takes a 4-quart container and then two 1-quart containers, three in all. Two 3-quart containers are better.
Dynamic programming gets it right by trying every last container for every amount. The fewest containers for amount a is 1 plus the fewest for a − s, taken over every container size s that fits. Filling the table from 0 upwards means every smaller answer is ready when it is needed.
function greedy(target, sizes) {
const used = [];
for (const s of [...sizes].sort((a, b) => b - a)) while (target >= s) { used.push(s); target -= s; }
return used;
}
function fewest(target, sizes) {
const best = new Array(target + 1).fill(Infinity), last = new Array(target + 1).fill(0);
best[0] = 0;
for (let a = 1; a <= target; a++) {
for (const s of sizes) {
if (s <= a && best[a - s] + 1 < best[a]) { best[a] = best[a - s] + 1; last[a] = s; }
}
}
const used = [];
for (let a = target; a > 0 && best[a] !== Infinity; a -= last[a]) used.push(last[a]);
return { count: best[target], used, table: best };
}
const sizes = [1, 3, 4];
console.log('greedy:', greedy(6, sizes));
const r = fewest(6, sizes);
console.log('dynamic programming:', r.used, '| table', r.table);
console.log('11:', fewest(11, sizes).used, '| 7 with only 3s and 4s:', fewest(7, [3, 4]).used);greedy: [ 4, 1, 1 ] dynamic programming: [ 3, 3 ] | table [ 0, 1, 2, 1, 1, 2, 2 ] 11: [ 3, 4, 4 ] | 7 with only 3s and 4s: [ 3, 4 ]
What this code does
greedy always takes the largest container that still fits, which gives three containers for an amount of 6. fewest fills a table in which each amount's answer is one more than the best answer for the amount minus some container size, and it records which size was used last. Following those records back from the target lists the containers, here two of size 3.
Recording the last choice for each subproblem, and following the records back from the final answer, is how almost every dynamic programming solution recovers not just the best value but the choices that give it.
Packing the van: the knapsack problem
The 0/1 knapsack problem is the classic dynamic programming problem. There is a set of items, each with a size and a value, and a container with a fixed capacity. Choose items, each at most once, so that their total size fits and their total value is as large as possible. For the hamper drive's last van, the items are donated crates, the size is how many floor spaces each crate takes and the value is how many meals it provides.
There are 2ⁿ possible selections of n crates. Dynamic programming avoids trying them all with a table best[i][c]: the most meals using only the first i crates within capacity c. For crate i there are two choices. Leave it, and the answer is best[i − 1][c]. Take it, if it fits, and the answer is its meals plus best[i − 1][c − size]. The table has (n + 1) × (capacity + 1) entries, each filled in O(1), so the whole algorithm is O(n × capacity).
const crates = [
{ name: 'Canned soup', space: 3, meals: 40 }, { name: 'Pasta', space: 2, meals: 25 },
{ name: 'Rice', space: 4, meals: 52 }, { name: 'Produce', space: 5, meals: 58 },
{ name: 'Cereal', space: 1, meals: 9 }, { name: 'Frozen meals', space: 4, meals: 49 },
];
function knapsack(items, capacity) {
const n = items.length;
const best = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
const { space, meals } = items[i - 1];
for (let c = 0; c <= capacity; c++) {
best[i][c] = best[i - 1][c]; // leave crate i
if (space <= c) best[i][c] = Math.max(best[i][c], meals + best[i - 1][c - space]); // take it
}
}
const chosen = []; // walk back to find the choices
for (let i = n, c = capacity; i > 0; i--) {
if (best[i][c] !== best[i - 1][c]) { chosen.push(items[i - 1].name); c -= items[i - 1].space; }
}
return { meals: best[n][capacity], chosen: chosen.reverse() };
}
console.log(knapsack(crates, 10));
console.log(knapsack(crates, 13));{ meals: 126, chosen: [ "Canned soup", "Pasta", "Rice", "Cereal" ] }
{ meals: 166, chosen: [ "Canned soup", "Pasta", "Rice", "Frozen meals" ] }What this code does
knapsack fills a table where each entry is the most meals possible using the first i crates in c spaces, either leaving crate i or taking it and adding its meals to the best result for the remaining space. Walking back through the table, a crate was taken wherever its row improved on the row above. With ten spaces the best load is 126 meals, which no simple rule such as taking the most meals per space is guaranteed to find.
O(n × capacity) is fast when the capacity is a modest whole number, as here. It is called pseudo-polynomial, because the work grows with the size of the capacity number rather than with the number of digits needed to write it. If capacity were measured in thousandths of a floor space instead of whole spaces, the table would be a thousand times larger. In general the knapsack problem has no known algorithm that is fast for every input, which is a reminder that dynamic programming speeds up many hard-looking problems but not all of them.
Comparing strings: edit distance
When families register for the grocery program, the same family is sometimes entered twice with slightly different spellings: Okafor and Okafur, Nguyen and Nguyễn, Larsen and Larson. The edit distance, or Levenshtein distance, between two strings is the fewest single-character insertions, deletions or substitutions that turn one into the other. Small distances between names on the same street are a good hint of a duplicate record for Lucy to check by hand.
The subproblem is d[i][j], the edit distance between the first i characters of one string and the first j of the other. If the characters at those positions match, d[i][j] = d[i − 1][j − 1]. Otherwise the last step was a substitution, a deletion or an insertion, so d[i][j] is 1 plus the smallest of d[i − 1][j − 1], d[i − 1][j] and d[i][j − 1]. The first row and column are the costs of building a string from nothing, which are just its length.
function editDistance(a, b) {
const d = Array.from({ length: a.length + 1 }, (_, i) => [i, ...new Array(b.length).fill(0)]);
for (let j = 0; j <= b.length; j++) d[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]) d[i][j] = d[i - 1][j - 1];
else d[i][j] = 1 + Math.min(d[i - 1][j - 1], d[i - 1][j], d[i][j - 1]);
}
}
return d[a.length][b.length];
}
for (const [x, y] of [['Okafor', 'Okafur'], ['Larsen', 'Larson'], ['Haddad', 'Hadad'], ['Silva', 'Novak'], ['', 'Ana']]) {
console.log(x.padEnd(7), y.padEnd(7), editDistance(x, y));
}Okafor Okafur 1
Larsen Larson 1
Haddad Hadad 1
Silva Novak 4
Ana 3What this code does
editDistance fills a table in which each cell is the cheapest way to turn the first i characters of one name into the first j of the other. Matching characters cost nothing extra, and a mismatch costs one plus the cheapest of the three neighboring cells, one for each kind of edit. The table has one cell per pair of positions, so comparing two names of length m and n is O(m × n).
The same table, with different rules, gives the longest common subsequence of two sequences, which is how diff tools and git work out which lines changed between two versions of a file. Spell checkers, DNA comparison and the "did you mean" suggestions in search boxes all use relatives of edit distance.
A recipe for dynamic programming
Gareth gives Mira five steps that work for most dynamic programming problems. Practicing them on small problems makes the big ones manageable.
| Step | Question to answer | Knapsack example |
|---|---|---|
| 1. Define the subproblem | What does one table entry mean, exactly? | best[i][c]: most meals from the first i crates in c spaces |
| 2. Write the recurrence | How is an entry built from smaller entries? | Leave crate i, or take it if it fits |
| 3. Set the base cases | Which entries are known without any choices? | No crates or no space: 0 meals |
| 4. Choose the order | Which entries must be ready before each one? | Row i − 1 before row i |
| 5. Read the answer and the choices | Which entry is the answer, and how are choices recovered? | best[n][capacity], then walk back |
The analysis follows from step 1: the running time is the number of table entries times the work per entry, and the memory is the size of the table, or less when only the previous row is needed. If the subproblem definition gives a table too large to fill, the problem may need a different idea, an approximation or a heuristic.
Try it yourself
Filling the garden bed
Complete ways(n) so that it returns the number of ways to fill a garden bed n units long with trays that cover 1 unit or 2 units, in order. There is 1 way for n = 0 and 1 way for n = 1.
Use a loop that keeps only the last two answers, so the function is O(n) time and O(1) memory.
function ways(n) {
if (n <= 1) return 1;
return ways(n - 1) + ways(n - 2);
}
console.log(ways(1), ways(2), ways(3), ways(8), ways(40));
console.log(ways.toString().includes('ways(n - 1)') ? 'recursive' : 'loop');Try it yourself
Fewest containers
Complete fewestContainers(target, sizes) so that it returns the fewest containers whose sizes add up exactly to target, or -1 if it cannot be done. Use a table filled from 0 up to target.
Greedy gives the wrong answer for 6 with sizes 1, 3 and 4.
function fewestContainers(target, sizes) {
let count = 0;
for (const s of [...sizes].sort((a, b) => b - a)) while (target >= s) { target -= s; count++; }
return target === 0 ? count : -1;
}
console.log(fewestContainers(6, [1, 3, 4]), fewestContainers(10, [1, 3, 4]), fewestContainers(7, [2, 4]), fewestContainers(0, [3]));Try it yourself
Is it the same family?
Complete editDistance(a, b) so that it returns the fewest single-character insertions, deletions or substitutions that turn a into b.
Fill a table with one more row than a has characters and one more column than b has, as in the lesson.
function editDistance(a, b) {
let diff = Math.abs(a.length - b.length);
for (let i = 0; i < Math.min(a.length, b.length); i++) if (a[i] !== b[i]) diff++;
return diff;
}
console.log(editDistance('Okafor', 'Okafur'), editDistance('Haddad', 'Hadad'), editDistance('Tanaka', 'Tanka'), editDistance('', 'Silva'));Common mistakes
MistakeAssuming greedy always gives the best answer.
InsteadIt does for standard coins but not for sizes like 1, 3 and 4. Prove greedy correct or use dynamic programming.
MistakeDefining the table entry vaguely.
InsteadWrite down exactly what one entry means before writing the recurrence; most bugs start there.
MistakeCounting the same combination of coins several times.
InsteadLoop over coin types on the outside so each combination is built in one fixed order.
MistakeKeeping the whole table when only the last row is needed.
InsteadKeep one or two rows to cut memory, unless you need the table to recover the choices.
MistakeExpecting dynamic programming to make every problem fast.
InsteadIt needs overlapping subproblems and a table of manageable size; knapsack with huge capacities is still slow.
Summary and key terms
- Dynamic programming solves problems with optimal substructure and overlapping subproblems by solving each subproblem once and storing the answer.
- Memoization does this top-down by caching recursive calls, and tabulation fills a table bottom-up in a loop, often keeping only the last row or two.
- Counting problems such as tray arrangements and ways to pay an amount build each count from smaller counts, with coin types looped outside so each combination is counted once.
- Greedy choices are correct for standard coin systems but fail for sizes such as 1, 3 and 4, where a table of fewest pieces gives the right answer.
- The 0/1 knapsack problem fills best[i][c] by leaving or taking each item and runs in pseudo-polynomial O(n × capacity) time.
- Edit distance fills a table over pairs of positions and helps find duplicate names; the longest common subsequence powers diff tools.
- Recording each subproblem's last choice and walking back recovers the chosen items.
- A five-step recipe defines the subproblem, recurrence, base cases, order and answer.
- dynamic programming
- Solving a problem by solving each overlapping subproblem once and building larger answers from stored smaller ones.
- optimal substructure
- The property that the best solution can be built from the best solutions of subproblems.
- overlapping subproblems
- Subproblems that a naive recursive solution would solve many times.
- tabulation
- Filling a table of subproblem answers from the smallest upwards in a loop.
- recurrence
- A rule that defines each answer in terms of answers to smaller subproblems.
- greedy algorithm
- An algorithm that always makes the choice that looks best at the moment, without reconsidering.
- 0/1 knapsack problem
- Choosing items, each at most once, to maximize total value within a capacity.
- pseudo-polynomial time
- Running time that grows with the size of a numeric input such as a capacity, not just with the number of items.
- edit distance
- The fewest single-character insertions, deletions or substitutions that turn one string into another.
- longest common subsequence
- The longest sequence of items that appears in the same order in two sequences, not necessarily together.
Practice problems
Work each problem on paper first, then reveal the answer to check.
What two properties make a problem suitable for dynamic programming?
Show answer
Optimal substructure and overlapping subproblems.
With containers of 1, 3 and 4 quarts, what does greedy give for 6 quarts, and what is best?
Show answer
Greedy gives 4 + 1 + 1, three containers; the best is 3 + 3, two containers.
How large is the knapsack table for 6 crates and 10 spaces?
Show answer
7 rows by 11 columns, 77 entries.
What is the edit distance between Larsen and Larson?
Show answer
1: substitute e with o.
How do you recover which items were chosen?
Show answer
Record or detect the choice made at each entry and walk back from the final answer.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.