Hello all and welcome back.
So in this video let us continue our discussion on dynamic programming.
And now let us try to calculate the time complexity of the tabulation approach we did in the last video.
So if you all remember in the last video we saw another approach through which we can solve our DP question.
And normally it is referred to as pure DP.
In this we created a DP.
You can see it as a list or an array okay.
A DP space where we were storing our answer so used to store.
Answer.
To subproblems.
Now this again is very important that we were storing the answer to subproblems in a bottom up manner.
Right.
So in a bottom up manner.
Now Overall it would be very easy because now there is no recursion or anything involved.
Let us go back to code and see what exactly will be the complexity of this approach.
Now if we see we are just calling a function, this is just some constant work which we are doing everyone.
So this is some k work.
Again, these are all some k work defining our array, defining our array or list of DP.
Then taking in the base cases all that is fine.
Along with that, now we are just running a loop okay.
So this loop as you can see it is going to run from two to n.
Now if my n is five, if it is ten, if it is 50, of course the number of iterations is going to increase.
So that means this particular loop is dependent on my n.
We have seen this relation a lot of times it's going to be big O of N and space wise.
Also, we can say that because we are defining a DP array or list, it's going to take a big Big-O of
n space like big O of N plus one, which is equal to big O of N only.
Again, it is pretty easy to calculate our complexity in this manner for a pure DP solution, but the
understanding of writing this solution is actually based on how well you know how to do recursion and
do the memoized approach, right.
So the approach using memoization is very important, so that we can use or finally write down our pure
DP solution.
Moving forward in questions we are going to follow this particular approach.
First we will write the recursive solution.
Then we'll convert that recursive to memoization.
And then to tabulation or pure DP.
Now one thing more everyone to understand.
It's not that always recursion will be at play.
If you are solving a question by DP, We will be seeing the example as well going forward.
The basic idea around DP is again the same.
If your solution depends on overlapping subproblems which you are able to solve, then we just try to
remember the overall solution.
So that is the thing which we need to understand and always remember.
The definition is something which is the truth.
Okay, so don't always feel that recursion is the only way of solving DP questions.
No.
Try to understand the intuition, the idea, the pattern, and what exactly the question is asking you
to do instead of remembering the solution.
Remembering the approach.
That is where I think you will get better benefit.
And as we do more and more question going going forward, you will get into clarity.
This whole thing will become clear so that you will be able to write better code.
Okay, so tabulation or pure DP.
Great everyone.
So pretty sure you must have understood the same.
Now we will be starting with lots of questions in DP through which your understanding will become more
and more clear.