A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times.
As an example, let's look at the fibonacci squence (the series where each number is the sum of the two previous ones—0,1,1,2,3,5,8...).
If we wanted to compute the nth fibonacci number, we could use this simple recursive algorithm:
We'd call fib(n-1) and fib(n-2) subproblems of fib(n).
Now let's look at what happens when we call fib(5):
Our function ends up recursively calling fib(2) three times. So the problem of finding the nth fibonacci number has overlapping subproblems.
Pass Your Interviews with My FREE 7-Day Crash Course
I'll teach you the right way of thinking for breaking down tricky algorithmic coding interview questions you've never seen before.
No prior computer science training necessary—I'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe if you hate it.