Welcome back, everyone.
Hopefully, the challenge was not too hard if you managed to figure it out, that's great.
If not, let's just do it together.
The first thing that we need to do is modify our initial calling function.
We're also going to modify what we pass into our recursive function as well.
So we might as well remove everything here and just start from the very top.
We're going to keep the const end because that's not going to change.
But now we're going to initialize some type of object that will save the values.
And I'm going to call it DPE for dynamic programming.
And it's going to be equal to an empty array as we know.
We want to match the data structure to whatever data structure we receive that we iterate through for
our answer.
Next, what we're going to do is we are going to return the same thing we had before.
So math dustmen.
Between calling our min cost.
On IE minus one, which receives the Costa, but now also our DPE.
As well as men cost.
I'm minus two, which now receives the cost as well as deep as well.
That's the main change to the original calling function, ask for our recursive function, we now have
to add the fact that we receive a DP.
Inside of our arguments and inside here, we need to think about what we're going to do to both retrieve
the appropriate value if it already exists, but also store the appropriate value if it also exists.
So first, I'm just going to remove this initial caller.
Our base cases actually stay the same.
Because these don't really have any type of scaling impact on our performance and they only suit to
help us, we know that that's not going to change.
What will change, though, is that what we have to do before we run the calculation?
We need to check if the value exists in DP already and we're going to store it in DP at the index.
So what we're going to say is that if the DP value at the current index is not equal to anything, so
if it is not undefined, so we'll say as long as I is not equal to undefined.
Because the value could be zero, so we can't just assume it'll be Truthy if this happens, then we
just want to return what we have at DPE at I.
Otherwise, we want to store the value.
There is no value here.
We have to calculate it manually.
So let's say I is equal to what we had before.
So it's going to be the cost that I plus the math dustmen.
Between our men cost recursive call on AI minus one passing and the same cost array and passing in our
current DPE.
Similarly, we're going to do the same thing for I minus two, same cost, the same DPE.
Once we started in the DPI, normally we just return this value, but instead we're going to return
the value that we've saved in DPI.
So we'll return DPI at EI.
And now this is our modified function, that's all it is.
What you want to think about now is what does this do to our performance?
Remember before that we had a space and time of two to the power of end.
Now, what we have instead is we've managed to lower down the number of iterations we have to do, because
if the value exists, we don't build out that branch, which means that this entire section where i3
gets calculated, this will actually not even run.
We're just going to end up retrieving the value in DPE.
So this entire branch has already been calculated before.
We're not going to do anything here.
Similarily I three here is also not even going to get calculated.
Because we've already memorized the value here and here I for as well.
We've already calculated everything here.
We're just going to retrieve the value that DPE has stored.
So what you see is that we save ourselves on so many calculations as essentially we just calculate everything
from AI all the way down to zero one time.
So what this means is that our time complexity goes down to O of N where N is the size of your array.
As for space, space also goes down to O of N because our recursion tree is only going to grow to the
size of N since as I mentioned, we're only doing N calculations and our DP is also going to be of size.
And because of course we're storing a value at every single index that exists inside the cossa.
So it's equal to the same length.
So it's two and you drop the two, you end up with n space and time are both O of end.
This is the full entirety of the top down approach.
You figure out the recurrence relation, you get the formula, you use the formula to derive an initial
recursive solution from this recursive solution.
You draw a state based tree or you mentally map out a state based tree and figure out where you're wasting
cycles.
Then you utilize some type of memorization where you create some data structure that's equal to the
object that you're iterating through or the data structure that you're learning through.
And then you fill it into your existing solution by replacing it where you need to either pull the value
out or calculate the value.
And then now you have a much faster, vastly optimized algorithm.
We went from two to the power of N down to O of N.
That is an incredible savings.
That's why dynamic programming is so powerful, but it's such an extensive step through process to get
to.
And this is just the top down process.
We can actually optimize our solution in such a way that we can go and save ourselves on our space complexity.
Time does not actually get any better at this point.
This is the best time complexity, but we can improve space complexity.
Remember, what I've mentioned is that up until this point, what we've done is known as the top down
approach.
From this top down approach, you've managed to identify what the top down tree build looks like here.
The next approach is going bottom up where you build from your base values at the very bottom here,
including your base cases, and you build up to a solution and you can do it in an iterative manner
instead of a recursive manner.
I do want to mention that this top down approach for your interview questions is enough.
It's very, very unlikely that in your interview they're going to expect you to go through the full,
deep process where you finish the top down approach and then transition to a bottom up approach.
Finding the bottom up is very challenging.
It's actually just as hard as finding the recurrence relation because you're looking for a new relationship
to rewrite your algorithm.
But what we're going to do at the very least, is explore what that path looks like, but I do want
you to know that it's not always expected that you are going to have to do the bottom up approach as
well.
Reaching this point should be your main focus with dynamic programming.
If you are constrained on time, if you have a lot of time, then of course practice the full entirety
of dynamic programming.
Doing it will only benefit you with getting a deeper understanding of why dynamic programming is a great
algorithmic paradigm.
But that's my warning for you.
So for us, let's try and figure out how we can convert this into the bottom up approach and why that
improves our space complexity.