Skip to content

level 8 · Core techniques

Dynamic Programming

Solve each small problem once, write the answer down, and never solve it again.

15 min 120 XP

what is it

Start here

Dynamic programming has a frightening name and a very simple idea: if you're going to solve the same small problem a thousand times, solve it once and write the answer down.

Take coin change. What's the fewest coins that make 6, using coins of 1, 3 and 4? The recursive answer is: pick a coin, then solve the smaller amount that's left. But that smaller amount comes up again and again down different branches — the naive recursion recomputes it over and over, and the work explodes exponentially.

So instead, build a table from the bottom up. Amount 0 needs 0 coins — free. Then for every amount upward: the best way to make `a` using a coin `c` is one `c` plus the best way to make `a − c` — an amount you have **already solved**. Reach back into the table, add one, done.

Watch the table fill. Each cell lights up its source — the smaller answer it was built from. Nothing is ever computed twice, and every cell is filled exactly once. That's the entire technique: **overlapping subproblems** solved once, and **optimal substructure** — the big answer being built out of small ones.

real-life analogy

Picture it

A climber leaving notes on the rocks

You're climbing a cliff with many routes and keep arriving at the same ledges. The first time you reach a ledge, you chalk the cheapest cost to get there. Next time you arrive from a different route, you don't re-climb — you read your own note. That chalk is the DP table.

interactive visualization

Watch it run

Type a target amount from 1 to 12. Coins available: 1, 3 and 4.

coins 1, 3, 4 — fewest needed to make each amount

0123456
coins
0
∞
∞
∞
∞
∞
∞

How few coins from {1, 3, 4} add up to 6? Build a table: one cell per amount from 0 up to 6. Amount 0 needs 0 coins — that's the one answer we get for free.

step 01/30

  • comparing
  • in final place
  • found it
1// Fewest coins that add up to `amount`.
2function coinChange(coins, amount) {
3 const dp = Array(amount + 1).fill(Infinity);
4 dp[0] = 0; // 0 coins make 0
5
6 for (const coin of coins) {
7 for (let a = coin; a <= amount; a++) {
8 // either the best we already had...
9 // ...or one `coin` plus the best for (a - coin)
10 dp[a] = Math.min(dp[a], dp[a - coin] + 1);
11 }
12 }
13
14 return dp[amount] === Infinity ? -1 : dp[amount];
15}

variables right now

coins
1 3 4
target
6
comparisons 0moves 0

the dry run · every step, in words

30 steps

complexity

What it costs

best case
O(n·k)
average
O(n·k)
worst case
O(n·k)
extra memory
O(n)

One cell per amount (n), touched once per coin (k). The naive recursion is exponential — it explores the same subproblems again and again. Filling a table turns a problem that would take longer than the universe has existed into one that finishes instantly.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Reaching for DP on any problem that looks hard.

    DP needs two specific things: the same subproblems must come up more than once (overlapping subproblems), and the big answer must be buildable from small ones (optimal substructure). No overlap, no benefit.

  • Getting the base case wrong.

    dp[0] = 0 — zero coins make zero. Everything else builds on that one free answer. A wrong base case quietly poisons the whole table.

  • Forgetting that some amounts may be impossible.

    Start every cell at infinity, meaning 'no way known'. If it's still infinite at the end, no combination of coins makes that amount — and you must return −1, not infinity.

  • Thinking greedy works here.

    Always taking the biggest coin fails: with coins 1, 3, 4 and a target of 6, greedy takes 4 then 1 then 1 — three coins. The real answer is 3+3, just two. Greedy is not DP.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+120 XP

01What two properties must a problem have for DP to help?

02Coins are 1, 3 and 4. What's the fewest that make 6?

03Why is the naive recursion for coin change so slow?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.