Algorithms
Dynamic Programming (Memoization)
O(n) time and O(n) space for Fibonacci with memoization — a huge improvement over plain recursion's O(2^n) time, at the cost of some memory for the cache.
The idea, in plain English
Dynamic programming is like writing an answer on a sticky note the first time you work it out. Next time someone asks the same question, you just read the note instead of redoing the work. This sticky-note cache is called 'memoization' — remembering answers to problems you already solved.
How it works
- 1Before you compute an answer, check a cache, like an object or dictionary, to see if you already solved this exact smaller problem.
- 2If the answer is cached, return it right away. You do not need to recompute it.
- 3If it is not cached, compute it, often by calling the function again on smaller problems. Save the result in the cache, then return it.
When you'd use it
Use it for problems that ask the same question over and over, such as Fibonacci numbers, counting paths on a grid, or coin-change problems. Plain recursion would redo the same work many times here.
Common beginner mistakes
- Forgetting to check the cache first, which quietly falls back to slow, repeated recomputation.
- In Python, using a mutable default argument like memo={}. It gets shared and reused across calls instead of starting fresh.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
fib(10) = 55
fib(20) = 6765Note: In Python, avoid a mutable default value like memo={}. It is the same trap as the default list in DFS. We use None instead, and create a fresh cache each time.
See it in motion
Ready. Press play to fill the table one cell at a time.
Not sure this is the right topic? See the learning paths → or where this leads →