Skip to content
Optimal Lab

DSA · interactive

Dynamic programming: solve small, reuse it

What is the fewest coins (1, 3, 4) that add up to an amount? Plain recursion asks the same small questions over and over. A table answers each one once, from 0 upward, and looks up the rest.

Filling amount 0 of 6

coins 1 · 3 · 4

  1. 00
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7. 6
  • best[0] = 0, no coins needed

Start with the base case: making 0 takes 0 coins.

Amount

1 of 7 cells
  1. 1

    Making 0 takes 0 coins. Every other answer is built on top of this one.

    best[0] = 0

  2. 2

  3. 3

  4. 4

Now solve it

Dynamic Programming: 18 problems

See all →

In production

Tools and technologies

Dynamic programming shows up wherever a big choice splits into smaller ones that repeat.

Not tied to one language — use these names when you search docs or design a system.