Subproblems and Overlapping Subproblems
Course launching August 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
SHOW SIDE BY SIDE GIF OF FACTORIAL VS FIB (the tree vs list is the difference in having overlapping problems) https://visualgo.net/en/recursion
From my experience, resources that teach dynamic programming gloss over subproblems and assume you already know them (or perhaps the teacher doesn't understand it well enough to put it in simple terms). You usually see a phrase like, "If you recognize overlapping subproblems, it's a great opportunity for dynamic programming." However without understanding what a subproblem is, you can't feel confident doing dynamic programming or possibly even recursion.
We previously saw that we could recursively solve for the factorial for any number
It basically took the following form (ignoring the base case for now):
factorial(n) = n * factorial(n - 1)
What we did was recognize a subproblem.
To find the factorial of any number
n, you can multiply
n * (n - 1)!.
So you need the number before the current
n to find the solution, but then you need the number before that to solve it, and so on until you reach the base case.
You repeat the same logic over an over from the base case up to the
n! you're looking for.
The only thing that changes is the input at each step, which will produce a different output.
The output for each step is passed to the function call that invoked it, and this function can then use it to calculate the result of its subproblem.
By building up the result to each subproblem, we can eventually calculate
n! of the original invokation.
If we wanted to calculate
factorial(1000), we don't need to actually know what
By specifying the correct base case and recursive case, result of all the preceding subproblems will produce the solution we need
Up to this point, we haven't discussed overlapping subproblems, because there aren't any in the factorial function. They are all subproblems called with unique values.
For overlapping subproblems to occur, our recursive function will be called with the same input multiple times. This most often happens when we have more than one recursive call in a recursive function.
For example, the logic for finding a Fibonacci number is the following:
fib(n) = fib(n - 1) + fib(n - 2)
We have subproblems where we can calculate the Fibonnaci number for any value
and all we need to do calculate the Fibonacci for all the values that come before.
We also have two recursive function calls to calculate it
fib(n - 1) and
fib(n - 2).
So if we wanted
fib(100) = fib(99) + fib(98),
fib(98) would separately generate all the numbers
Not only that, it would create that repeated logic for each step in the call stack.
If we look at
fib(5), we can see the repeated calculations:
With dynamic programming, we use memoization to store the results of these repeated steps so we only solve each overlapping subproblem once.
Table of Contents