Graphs and dynamic programming · Lesson 21 of 23
Dynamic programming: the idea
Problems made of repeating smaller problems: top-down memoization and bottom-up tabulation.
DP isn't an algorithm but a way of thinking. It applies when a problem:
1. Splits into smaller problems of the same kind (like recursion). 2. Those smaller problems repeat, so we store each answer once.
The crucial step is defining the state ("what exactly is dp[i]?"), then the recurrence linking it to smaller states.
Example: robbing a street
Houses in a row hold money, and you can't rob two adjacent houses. best[i] = the most you can take from the first i houses. At house i you either skip it (best[i-1]) or rob it, which rules out the one before (best[i-2] + money[i]):
best[i] = max(best[i-1], best[i-2] + money[i])
const money = [2, 7, 9, 3, 1]
// Top-down: the recursion as you'd write it, plus a memo
function robTop(i, memo = new Map()) {
if (i < 0) return 0
if (memo.has(i)) return memo.get(i)
const value = Math.max(robTop(i - 1, memo), robTop(i - 2, memo) + money[i])
memo.set(i, value)
return value
}
// Bottom-up: fill the table from the smallest case
function robBottom() {
const best = new Array(money.length + 1).fill(0)
best[1] = money[0]
for (let i = 2; i <= money.length; i++) best[i] = Math.max(best[i - 1], best[i - 2] + money[i - 1])
return best[money.length]
}
// Each step only needs the last two values: O(1) memory
function robLean() {
let prev = 0, cur = 0
for (const m of money) [prev, cur] = [cur, Math.max(cur, prev + m)]
return cur
}
console.log(robTop(money.length - 1), robBottom(), robLean())| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
money | — | 2 | 7 | 9 | 3 | 1 |
best | 0 | 2 | 7 | 11 | 11 | 12 |
best[3] = max(7, 2 + 9) = 11, and best[5] = max(11, 11 + 1) = 12 (2 + 9 + 1).
Steps for any DP problem
1. State: what dp[i] (or dp[i][j]) means in words.
2. Recurrence: how is dp[i] built from smaller states? (Think about the "last decision".)
3. Base cases: dp[0], dp[1].
4. Order: compute small before large.
5. Answer: dp[n]? Or the largest value in the table?
6. Save memory if each step needs only the last few values.
Complete the code
Complete "climbing stairs": one or two steps at a time, how many ways reach step n?
function climb(n) { let a = 1, b = 1 // ways to reach step 0 and step 1 for (let i = 2; i <= n; i++) { const c = + a = b b = c } return b }
Exercise
Write fewestCoins(coins, amount): the fewest coins making the amount (coins may repeat), or -1. It must print 2 -1 0.
Expected output: 2 -1 0
function fewestCoins(coins, amount) {
}
console.log(fewestCoins([1, 3, 4], 6), fewestCoins([2], 3), fewestCoins([5], 0))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.