Hey there and welcome back!
In the previous video, we discussed that writing the recursive solution helps us to come up with the
bottom up approach or the tabulation approach.
Now, why is this the case?
The best way to understand this is by showing the benefits of this in an actual coding interview question,
and we will see this in action soon when we start attempting dynamic programming coding interview questions.
But over here, let me give you three reasons.
The first reason is that writing the recursive solution first helps us to understand the subproblems.
It also helps us to understand the transition formula as well as it helps us to recognize the necessary
base condition.
And this also can be used in some interesting way.
When we come up with the tabulation approach.
Let's take a quick look at these three points over here.
And we are just getting introduced to these.
And you will be able to solidify what we mean over here when we actually start solving dynamic programming
coding interview questions.
So let's get started.
So the first benefit is that writing the recursive solution helps to understand the subproblems.
Any recursive solution inherently breaks down a problem into smaller subproblems.
And because of that, if we first write the recursive solution, we will develop a clear understanding
of what these subproblems are for the coding question at hand.
The second benefit of writing the recursive solution first is that it helps us to understand the transition
formula.
With transition formula, we mean how do we use the subproblems or solutions to the subproblems to come
up with the solution to the original problem?
Now, the way the recursive calls are made helps us in identifying the transition formula or the recurrence
relation.
Now this is another benefit of first writing the recursive solution.
Finally, if we first write the recursive solution, we would have written the base conditions, because
any recursive solution has a base case.
And when we come up with the bottom up approach or the tabulation approach, the base case over here
or the base conditions over here would be the initial conditions in your dynamic programming table.
Now, what a dynamic programming table is, is something that we will soon see when we start to solve
DP problems.
But again, over here we are just developing an intuition.
So do remember that when we come up with the bottom up or tabulation approach, as the name suggests,
over here we will be having a DP table.
And then in many cases it's very easy if you have written the recursive solution first, because we
can just use the base case of the recursive solution to fill out the initial conditions in the DP table,
which is typically something that we fill over here, like for example, these rows would be initialized
to zero, etc. and again it varies based on the coding interview question.
In the next video, let's go ahead and discuss how can we identify whether a coding interview question
is to be solved using dynamic programming or not?
And then we'll get started with applying all that we learned in solving actual DP coding interview problems.