Overlapping subproblems
Overview
A problem has overlapping subproblems if a naive recursive solution calls the same subproblem with the same arguments more than once.
It tells you when caching (memoization) will speed up an algorithm, turning an exponential time complexity into polynomial time.
Where used: Dynamic Programming algorithms, Recursive algorithms that recalculate results
Why learn this
- It is the first diagnostic test to determine if Dynamic Programming will help.
- You will learn to recognize why a simple recursive Fibonacci function is dangerously slow.
Common mistakes
- Applying DP to all recursive problems: Dynamic Programming only helps if subproblems overlap. Plain merge sort makes recursive calls, but each `(lo, hi)` pair is visited exactly once, so caching buys nothing.
Recall questions
- What does it mean for a problem to have overlapping subproblems?
Understanding checks
Does Dynamic Programming speed up EVERY recursive algorithm? Why or why not?
No. Dynamic Programming only speeds up recursive algorithms that have overlapping subproblems. If each subproblem is distinct (like in merge sort), caching does nothing.
Understanding when NOT to use DP is just as important as knowing how to use it.
If you calculate `fib(5)` using naive recursion, how many times is `fib(2)` evaluated?
Three times.
`fib(5)` calls `fib(4)` and `fib(3)`. `fib(4)` calls `fib(3)` and `fib(2)`. The first `fib(3)` calls `fib(2)` and `fib(1)`. The second `fib(3)` calls `fib(2)` and `fib(1)`. Total: 3 times.
Practice tasks
Add an operation counter
Modify this naive Fibonacci function to increment a global counter every time it is called. See how fast the counter grows for `n=10` vs `n=20` to prove overlapping subproblems.
Challenge
Identify Overlap
Look at the recursion tree for `fib(4)`. Write down the number of times `fib(1)` is called.
Continue learning
Previous: Recursive tree thinking
Next: Optimal substructure
Next: Memoization (top-down)