Hey there and welcome back!
So far we have discussed recursion and we have also thoroughly discussed backtracking.
Let's now get started with another algorithmic approach called dynamic programming.
Now dynamic programming can be used to solve many problems that can be solved with recursion in a better
manner.
Now for this, let's take an example.
Let's take the question where we are asked to identify the nth Fibonacci number.
Now the Fibonacci series has the relation that f of n is equal to f of n minus one plus f of n minus
two.
Now we will see this in greater detail in a future video.
But over here, let's just use it to develop an intuition regarding why dynamic programming is better
than just plain simple recursion in many coding interview questions.
So for the Fibonacci series, f of n is equal to f of n minus one plus f of n minus two.
And it's also given that in this series, the first term or the zeroth term is zero, and the next term
is one.
So we have zero and then we have one.
And then notice over here f of n is equal to f of n minus one plus f of n minus two.
So the next term would be the sum of the previous two terms.
So over here we would get zero plus one which is one.
And then the next term would be the sum of these two terms.
So one plus one is equal to two.
And then we'll have three because one plus two is three.
And the next term would be five because two plus three is five.
And then we'll have eight because three plus five is eight.
And it goes on in this manner.
Now imagine that we have written a recursive solution to find the nth Fibonacci number.
Let's say n is equal to five.
Now f of five.
Let's say that's what we want.
So f of zero is zero, f of one is one, f of two is one, f of three is two.
And notice over here f of five is five.
So we are going to write a recursive function to find f of n.
So for that let's first draw the recursive tree of the solution that we could write.
And for simplicity sake let's just take n to be equal to five.
So we want to find f of five.
And because f of five is equal to f of four plus f of three, we would have to recursively call the
function that finds this with a smaller input.
So we would have to call f of four and f of three.
Now to find f of four, we would have to recursively call f of three and f of two.
Similarly, to find f of three, we would have to call f of two and f of one for f of two.
We would have to call f of one and f of zero.
Now over here we have f of two.
For this again we would have to call f of one and f of zero.
And over here we have f of three.
So for that we would have to call f of two and f of one.
And for finding f of two again we would have to call f of one and f of zero.
Now again this would be the recursive solution that we would write.
And we can stop when we hit the base case where n is either 0 or 1, because we know f of zero is zero
and f of one is one.
So these two would be returning.
So f of one will return, f of zero will return.
And we would find the value of f of two.
And this would return to f of three.
And it would go on in that manner.
Now notice over here in this simple recursive approach we are calculating for example f of three two
times f of two is being calculated over here and over here and over here.
So notice that we are calculating the same f of n multiple times.
For example, f of three is calculated twice, f of two is calculated thrice, etc..
Now this is where dynamic programming becomes quite handy.
Now instead of calculating this again and again, why don't we just store it to avoid the recomputing?
Now this over here is dynamic programming or it is one approach in dynamic programming.
So dynamic programming is just recursion plus storage.
Now again this is one of the approaches of dynamic programming which is what we call memoization.
So memoization is just writing the normal recursive solution.
But then when we find something that's useful later we will just store it.
So when we come to this branch, we would not go all the way over here.
We would just directly return the value of f of three, because we have already calculated and stored
it at this instance.
So this is what we call memoization, and it is the first approach that we will discuss in dynamic programming.
The second approach that we will discuss in dynamic programming is what is called tabulation.
Now just to develop an intuition about this, again, let's take a look at the Fibonacci series question.
Notice over here that to find f of five we had to ultimately find f of four, f of three, and f of
two, and again f of one and f of zero is something that we already know.
Now what if we had a table that looked something like this.
And again, this is called tabulation for that particular reason that we would be using tables when
we're discussing this approach.
So what if we had a table over here and let's say the indices went from zero right up to five.
And then to find F of five, we would just go ahead and find f of two, f of three, f of four, and
then proceed and find f of five.
So this approach is what we call tabulation.
Now we will discuss these two approaches in much greater detail in future videos.
But over here we're just trying to get introduced to dynamic programming.
And we have built a good intuition about why dynamic programming is a very efficient way of solving
coding.
Interview questions.
So the two dynamic programming approaches that we have discussed over here are memoization, which is
basically recursion plus storage and tabulation, which is using a table.
And then we would just find values to find the final solution that we want to find.
Notice that in tabulation as well we are not calculating these values multiple times, but rather we
are just calculating it once.
So f of two is calculated only once.
F of three is only calculated once, and f of four is also only calculated once and again.
Whenever we calculate these values, we store them over here, and we use these values to find the answer
that is asked of us.
So what is basically dynamic programming?
Dynamic programming is basically a method to solve complex problems, where problems exhibit two characteristics
which are overlapping subproblems and optimal substructure.
Now let's again take a look at the Fibonacci series question.
And let's try to understand these two terms over here.
The first term is overlapping subproblems.
And we have seen that we were calculating f of three multiple times and f of two multiple times.
So this is what we call overlapping subproblems.
And to make this process efficient we discussed that we would just store these values when we compute
them.
And in that manner we can avoid recomputing them again and again.
So the first characteristic of dynamic programming questions is that there would be overlapping subproblems.
And hence, by just making the slight tweak of storing things that we compute, we will be able to significantly
improve the time complexity.
The second characteristic of problems which can be solved using dynamic programming is that they will
exhibit optimal substructure.
Now what do we mean with optimal substructure?
Optimal substructure means that solutions to a problem can be constructed from optimal solutions of
its subproblem.
Now what does this mean over here?
Now, in the case of the Fibonacci question, notice that to find f of five, for example, we can just
find f of four and f of three, which are subproblems.
And these solutions can be used as it is by just adding these two together to find the value of f of
five.
So in this case optimal solutions to the subproblems which are.
These two over here were used to find the optimal solution of the problem which is f of five.
So this is what we call optimal substructure.
Now let's quickly take a case where a coding interview question can be solved with recursion, but cannot
be solved with dynamic programming because the problem does not have optimal substructure.
To just thoroughly understand this now, we have seen that the Fibonacci question has optimal substructure,
and that's what we have just now discussed.
But a question which does not have optimal substructure is, for example, the Tower of Hanoi problem,
which we had discussed under recursion.
Now in the Tower of Hanoi problem, we had three rods and we had to move the given number of disks,
the n number of disks from the first rod to the last rod, and we could take the help of an auxiliary
rod.
Now, the conditions were that you could not place a bigger disk on a smaller disk, and you can just
move one disk at a time.
Now in this question, remember what we discussed was that we would first move n minus one disks from
rod number one to rod number two.
And then we would move the biggest disk over here from rod one to rod three.
And then finally we would move n minus one disks from rod two to rod three.
So this is the approach that we have discussed for the Tower of Hanoi problem.
Now notice over here solving n minus one disks problem or the sub problem is not used as it is for solving
the problem where there are n disks, because if there had been n minus one disks, we would not be
moving those n minus one disks to row two.
But because we have n disks, we are moving n minus one disks from rod one to row two, and later we
are moving them from here to here.
But again notice the optimal solution of the sub problem is not used for solving the problem.
So again that's the definition of optimal substructure.
The optimal solution to a problem can be constructed from optimal solutions of its subproblems.
Again notice over here if we had n minus one disks we would not move n minus one disks from rod one
to rod two.
Rather, we would move n minus two disks from rod one to row two, or rather one disk less than the
total number of disks.
So notice the optimal solution for the problem where we have n minus one.
Disks cannot be used for solving the problem where we have n disks.
We are using recursion to solve this problem, but we cannot use dynamic programming to solve the Tower
of Hanoi problem because it does not.
The problem does not exhibit optimal substructure.
So quickly.
Summarizing, we discussed the two approaches in dynamic programming that we would be discussing.
The first one is recursion plus storage, which is what is called memoization, and the second approach
is called tabulation.
We also discussed that dynamic programming can be used in coding interview questions, where the problem
exhibits two characteristics.
The first characteristic is overlapping subproblems, and the second characteristic is optimal.
Substructure.
In the next video, let's discuss the approach that we will take in this course to master dynamic programming.