Welcome back, everyone.
In the last video, I mentioned that there is a further optimization we can make when we realized that
we're only leveraging the last two stored values inside of our DP as we iterate through AI to end.
What we can do now is just replace this deep scaling array with two variables instead.
So to start, I'm just going to erase all of the code.
That is irrelevant because this is the part of it that we're going to rewrite.
I'm also going to get rid of the space and time complexity here.
Just remember that it was O of end.
Next, what we're going to do is just think about the two variables we need to initialize when we start
this value.
DP one, which is what I'm going to call the first variable.
Is going to actually be equal to cost at zero because this is the starting variable that we need to
store.
Secondly, then you can assume that DP two is going to be equal to cost at one.
Now that we've initialized our two DP variables, we can just run through the iteration like we did
before here.
We're going to use the same for loop, except we're going to initialize at two instead of zero, because
essentially what we did when we set up one in two was we cast the variables as the first two instances
of I we don't need to generate DP's for them.
That's what these two lines have literally done for us.
So with AI starting at two, we're going to go up to end the same way.
And I plus plus and now inside, what we want to do is generate the current value for AI.
So here it's going to utilize the two values at our DP.
So it's going to be cost at AI plus math dot min.
DP won.
And DP to.
Once we've generated and figured out what this current value is for, I, we need to replace our deep
one.
So first, what we're going to do is say that DPE one is equal to DPE two, because as we know from
the tree, when we use DPE one and two to generate the current value, we're going to use these two
now to generate this value, which means that this DPE one value is no longer needed.
Instead, this value is going to be the new DPE one.
This value we just generate.
It is the new DPE two or just keeping track of the two most recent values.
So that's why DPE one is now equal to TPE two and two is equal to our current value.
And that's all we need to do, just like that, we've generated and built up the same deep and of course,
the final answer that we return is just going to be the men of these two values.
So we're just going to return math to men between DPE one and deep two.
Once again, the reason why this happens is because the last two values that we've sought should be
the deep values for these last two variables inside of our staircase.
And this is the optimization.
Now, let's compare the space and time, if we look at our time complexity, first we notice that there's
no real optimization here.
We're still going to loop over the majority of N, but we're only going to do it once still.
So here it's still O of N, but when we look at our space complexity, we have no scaling data structures
anymore.
Instead, we just initialize to static variables, which means that we ended up with an O of one space
complexity, which is an amazing improvement over are even very first recursive solution.
If you think back, they were both two to the end here.
We've brought this down to of non-linear and of one that is incredible performance, constant space
and linear time.
That is one of the best possible solutions.
And this is why dynamic programming is so powerful as an algorithmic paradigm.
If you think about it, the very nature of the fact that we have to generate all the possible optional
solutions that could exist for a given question and then pick the best one from amongst them, that
by default sounds like a very computationally expensive endeavor.
But through dynamic programming, we're able to bring that down to such a drastically performance solution.
So here is the key that you have to remember, there are so many steps of dynamic programming, the
first one begins with identifying the recurrence relation formula that you can then use to build the
recursive function from the recursive function you want to build at top down and determine if there
is an optimization using memorisation that can help you.
Once you see that full top down solution, it's easy for you to extrapolate out the bottom up solution
because you know that if you're going top down, there's definitely a way to go bottom up.
As long as you analyze the correct base cases that you might have, most of the time you'll have these
base cases and they'll help you think about that bottom up approach.
Once you've understood what that is, you figure out the bottom up tree is and then you derive it ideally.
Then you look at your DPI and see if there is any wasted usage of space inside of your scaling DPI.
If there is, you reduce it to the parts that you only need and you're able to bring down to at least
the next level of space complexity with our own notation.
This is dynamic programming and this is the power of it.
If this whole process seems a little bit still kind of vague to you, don't worry, we're going to practice
a lot more.
So just keep this whole step by step, stage by stage process in your mind.
And always remember that with your interviews, you may not require going through the entire dynamic
programming step to get to this final optimized solution.
A lot of the times you can just finish the full top down solution with the memorization.
The bottom up is kind of hard to get to within the tight time frame of an interview question.
However, if you're able to articulate what that next step of going from top down to bottom up brings
in terms of its benefits and even just understanding the process of going from that top down tree to
this bottom up tree, if you're able to just articulate this stage of it, where you logically thinking
about it but not coding it out, that is oftentimes enough for your interviewer to know that you could
have solved the problem had you had more time.
And that is often enough for them to pass you through the interview so deeply.
Understand the process that we took to break down this dynamic programming problem and we'll get more
practice with the next problem.