Hey there and welcome back.
In this video, let's discuss what approach should one take to be able to solve dynamic programming
based coding interview problems?
Now, when it comes to dynamic programming, many people directly start to draw a table like this.
And then they put some initial values over here and go about it in this manner.
Now, this is the wrong approach of approaching dynamic programming questions.
All right.
So they're trying to directly start with the tabulation approach.
But then the problem is that you can memorize a few questions in this manner.
But then when you're presented with a new problem you will not be able to solve it.
So we will not be following this approach in this course, but rather the approach that we will be following
is that first we will write the recursive solution to any dynamic programming question.
And once we have written the recursive solution, we will be able to memorize it.
Because remember memoization is just recursion plus storage.
So after we are done with writing the recursive solution, we will just add a few lines of code to come
up with the memoization approach.
Again, remember this is just recursion plus storage, so we would just need to add a few lines to the
recursive solution to come up with the memoization solution.
Now the memoization solution is also called the top down solution.
Once we are done with this, we will proceed to step number three, where we will use what we have learned
over here to come up with the tabulation or bottom up approach.
So again, the tabulation approach is where you write a table and it's an iterative approach.
It's not a recursive approach.
Now remember don't directly start with the tabulation approach, but rather first write the recursive
approach.
Then come up with the memoization and use these two to efficiently come up with the tabulation approach.
Once we have written the tabulation approach, we will optimize this and come up with the space optimized
tabulation approach.
So these are the various steps that we will take in this course to understand various dynamic programming
coding patterns thoroughly.
Now, if you are not familiar with terms such as memoization and tabulation, don't worry about it.
As we go on with the course, we will be discussing this multiple times and in detail for various coding
interview questions, and then this will become second nature to you.
Just remember, memoization is also called top down approach.
And the tabulation approach is also called the bottom up approach.
Remember, we had previously discussed that in dynamic programming, coding interview questions occur
as part of patterns.
Now, if you have taken these steps for, let's say, the first question in a series of questions which
are of the same pattern, then for the second or third question, you will be able to directly come
up with the tabulation or bottom up approach, because you have built a good intuition and good understanding
of why this actually works.
So again, remember if you encounter a deep question and if you are not able to solve it, take these
steps.
First, write the recursive solution, then memorize it and use the understanding that you gain from
these two steps to come up with the tabulation approach.
Let's now take this one step further and let's compare the top down and bottom up approaches.
So over here I have a table.
Now remember memoization is the top down approach.
And tabulation is the bottom up approach.
Now, there is an easy technique that I use to not confuse between these two.
So notice over here we have a T for top down and for tabulation.
Also we have a T.
So I just remember that there is only one T at each site.
So let's say I want to recollect whether tabulation is top down or bottom up.
So what I think is that there is already a T, so I cannot have one more T.
So it has to be a B which is bottom up.
So again, this is just a quick way to correctly relate tabulation as the bottom up approach.
So memoization is the top down approach and tabulation is the bottom up approach.
Now let's compare between these two to solidify our understanding about these two approaches.
Now memoization is called the top down approach because in memoization we start with the original or
large problem which is called the top part.
And then we proceed recursively till we hit a base case.
And then we start returning and start computing the answer.
But when it comes to tabulation, it's called bottom up because it starts with the smallest subproblem.
And then it solves this.
And then it uses this to solve larger problems.
And again the smallest subproblem is what figuratively is called bottom of the problem hierarchy.
Now we will see this more often when we solve actual coding interview questions.
But over here let me just give you an intuition of what this actually means.
We had seen previously the Fibonacci question where we had various branches like this right now.
Remember in the recursive approach, the algorithm would go down a branch, and then once it hits a
base case, it will start computing and returning.
So that's why over here we can say that it starts with the original or large problem which is over here.
And then it goes down.
So this is called the top down approach.
But for the Fibonacci question we had also discussed that we could theoretically just have a table like
this.
Let's say we are trying to find f of five.
So we have a table over here.
And we know that f of zero is zero and f of one is one.
And then we just go ahead and find f of two which is adding zero and one.
That's one.
And then we find f of three which is adding these two which is two.
So in this case notice that we are starting over here by finding f of two.
And we are filling these to find the answer of f of five.
So that's what we say over here.
Tabulation starts with the smallest subproblem which is called figuratively the bottom of the problem
hierarchy.
And that's this place over here.
So again we have seen an interesting distinction between memoization and tabulation.
Now let's take a look at one more interesting point.
Remember memoization is a recursive approach.
It's just recursion plus storage.
But tabulation is an iterative approach.
So we are just iterating from two up to five.
And we keep calculating these values and we store them over here.
So in this video we have discussed the approach which is ideal to master dynamic programming coding
interview questions.
And we have also discussed the difference between memoization and tabulation when we discussed the approach,
which is ideal for mastering dynamic programming questions, we mentioned that it's ideal to first start
with the recursive solution and then memoize it before we proceed and write the tabulation approach.
In the next video, let's develop some intuition regarding why writing the recursive solution and then
memorizing helps us to effectively come up with the tabulation approach.