DSA Patterns Made Simple · Heaps, Backtracking and Dynamic Programming
Dynamic Programming: Remember Smaller Answers
When a problem's answer is built from answers to smaller versions of itself, and those smaller answers repeat, store them. Climbing stairs, house robber and coin change all use the same three questions.
The problem
Climbing Stairs: you can climb 1 or 2 steps at a time. How many different ways are there to reach step 10? To reach step 10, your last move came from step 9 or step 8, so ways(10) = ways(9) + ways(8). A plain recursion recomputes ways(5) dozens of times; for step 50 it would take ages.
How to spot it
- "How many ways…", "minimum cost / coins / steps", "maximum profit / value"
- Choices at each step that affect what's possible later (take it or skip it)
- A recursive solution that recomputes the same smaller problems (overlapping subproblems)
- Input sizes around 1,000 to 10,000, which fits an O(n) or O(n·k) table
The idea
Answer three questions, and the code writes itself:
- What is the state? What does
dp[i]mean, in words? ("the number of ways to reach step i", "the most money from the first i houses") - What is the recurrence? How is
dp[i]built from smaller entries? (dp[i] = dp[i-1] + dp[i-2]) - What are the base cases? The smallest answers you know directly (
dp[0] = 1,dp[1] = 1).
Then fill the table from small to big (bottom-up). Or write the recursion and cache its results (top-down memoisation; in Python, @cache). Both give the same answer.
It's like keeping a notebook of results while doing your taxes: once you've worked out a subtotal, you never redo it.
The template
dp = [0] * (n + 1)
dp[0] = BASE # 3. base cases
for i in range(1, n + 1):
dp[i] = best_of(dp[i - 1], dp[i - 2], ...) # 2. recurrence
return dp[n] # 1. state: dp[i] = answer for the first i items
const dp = new Array(n + 1).fill(0);
dp[0] = BASE; // 3. base cases
for (let i = 1; i <= n; i++) {
dp[i] = bestOf(dp[i - 1], dp[i - 2] /* ... */); // 2. recurrence
}
return dp[n]; // 1. state: dp[i] = answer for the first i items
Worked example
Three classics with the three questions answered in comments.
def climb_stairs(n):
# state: ways[i] = ways to reach step i; recurrence: from i-1 or i-2
ways = [0] * (n + 1)
ways[0] = ways[1] = 1 # base cases
for i in range(2, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]
def rob(houses):
# state: best[i] = most money from the first i houses
# recurrence: skip house i-1 (best[i-1]) or rob it (best[i-2] + its money)
best = [0] * (len(houses) + 1)
for i in range(1, len(houses) + 1):
best[i] = max(best[i - 1], (best[i - 2] if i >= 2 else 0) + houses[i - 1])
return best[-1]
def coin_change(coins, amount):
# state: fewest[a] = fewest coins that make amount a (inf = impossible)
# recurrence: try every coin as the last one
fewest = [0] + [float("inf")] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
fewest[a] = min(fewest[a], fewest[a - c] + 1)
return fewest[amount] if fewest[amount] != float("inf") else -1
print("ways to climb 5 steps:", climb_stairs(5))
print("ways to climb 40 steps:", climb_stairs(40))
print("rob [2, 7, 9, 3, 1]:", rob([2, 7, 9, 3, 1]))
print("coins for 11 with [1, 2, 5]:", coin_change([1, 2, 5], 11))
print("coins for 3 with [2]:", coin_change([2], 3))
Output
ways to climb 5 steps: 8 ways to climb 40 steps: 165580141 rob [2, 7, 9, 3, 1]: 12 coins for 11 with [1, 2, 5]: 3 coins for 3 with [2]: -1
function climbStairs(n) {
// state: ways[i] = ways to reach step i; recurrence: from i-1 or i-2
const ways = new Array(n + 1).fill(0);
ways[0] = ways[1] = 1; // base cases
for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2];
return ways[n];
}
function rob(houses) {
// state: best[i] = most money from the first i houses
// recurrence: skip house i-1 (best[i-1]) or rob it (best[i-2] + its money)
const best = new Array(houses.length + 1).fill(0);
for (let i = 1; i <= houses.length; i++) {
best[i] = Math.max(best[i - 1], (i >= 2 ? best[i - 2] : 0) + houses[i - 1]);
}
return best[houses.length];
}
function coinChange(coins, amount) {
// state: fewest[a] = fewest coins that make amount a (Infinity = impossible)
// recurrence: try every coin as the last one
const fewest = [0, ...new Array(amount).fill(Infinity)];
for (let a = 1; a <= amount; a++) {
for (const c of coins) if (c <= a) fewest[a] = Math.min(fewest[a], fewest[a - c] + 1);
}
return fewest[amount] === Infinity ? -1 : fewest[amount];
}
console.log("ways to climb 5 steps:", climbStairs(5));
console.log("ways to climb 40 steps:", climbStairs(40));
console.log("rob [2, 7, 9, 3, 1]:", rob([2, 7, 9, 3, 1]));
console.log("coins for 11 with [1, 2, 5]:", coinChange([1, 2, 5], 11));
console.log("coins for 3 with [2]:", coinChange([2], 3));
Output
ways to climb 5 steps: 8 ways to climb 40 steps: 165580141 rob [2, 7, 9, 3, 1]: 12 coins for 11 with [1, 2, 5]: 3 coins for 3 with [2]: -1
Plain recursion for 40 steps makes over 300 million calls; the table needs 40 additions.
Common mistakes
- Not writing down what
dp[i]means. Most DP bugs come from a fuzzy state. Say it in one sentence first. - Greedy instead of DP. "Always take the biggest coin" fails for coins
[1, 3, 4]and amount 6 (greedy: 4+1+1, best: 3+3). - Wrong base cases, often off by one (
dp[0]vsdp[1]). - Keeping the whole table when you don't need it. If
dp[i]only uses the last two entries, two variables give O(1) space. Optimise only after it works.
Practice
- Climbing Stairs (easy)
- House Robber (medium)
- Coin Change (medium)
- Longest Increasing Subsequence (medium):
dp[i]= longest increasing run ending at i.
Key points
- DP = recursion + remembering answers to repeated subproblems.
- Answer three questions: state, recurrence, base cases.
- Bottom-up table or top-down memoisation; same result.
- When greedy fails on a counter-example, try DP.
Practice questions
What are the three questions to answer before writing a dynamic programming solution?
Answer
What the state means (what dp[i] stores, in words), the recurrence (how dp[i] is computed from smaller states) and the base cases (the smallest answers known directly).
Give an example where a greedy coin-change approach fails.
Answer
Coins [1, 3, 4] and amount 6: greedy takes 4, then 1 and 1 (three coins), but 3 + 3 uses two. DP tries every coin as the last one and finds the minimum.
Open in the app to mark lessons complete, take notes and track your progress.