Subproblems and Overlapping Subproblems
Course launching November 17, 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.
From my experience, resources that teach dynamic programming gloss over subproblems and assume you already know them (or perhaps don't know how to teach it). 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 implementing dynamic programming or possibly even recursion.
I'll first define it, and then we'll walk through it step-by-step. Solving subproblems means we take a function and call it multiple times with different input values. We start with the smallest value (bottom-up) or recursively decrease the input (top-down) until we reach the base, and we then combine the results of all the function calls.
We previously saw that we could recursively solve for the factorial for any number
It 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)!.
And then this repeated because
(n - 1)! = (n - 1) * (n - 2)!.
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.
The image below is a visual for factorial recursion.
Each of the steps where you change the input is solving a different subproblem.
You combine them by multiplying each current number times the result of the subproblem before it to eventually calculate
So to explicitly state what's happening, we can say
4! = 4 * 3! which is
4! = 4 * 3 * 2! which is
4! = 4 * 3 * 2 * 1.
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.
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, the result of all the preceding subproblems will produce the solution we need.
Up to this point in this article, 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 Fibonacci number for any value
so then to calculate any given Fibonacci number, we just need the results of the Fibonacci numbers before it.
We require two recursive function calls to calculate a number:
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
fib(99) = fib(98) + fib(97) and
fib(98) = fib(97) + fib(96).
Each step generates many more function calls using the same input, and this branches outward with each nested step doing the same.
If we look at
fib(7), we can see the repeated calculations:
The items highlighted in blue are functions calls that happen multiple times. These are the overlapping subproblems. Visualizing the recursive calls as a tree, the branching is a sign that we'll have subproblems that overlap.
On the other hand, when calculating the factorial, we have subproblems but we don't have subproblems that overlap. So instead of creating a tree structure with branching as the representation, it simply forms a straight line.
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