Welcome back.
Now this is the recursive solution that we had written previously.
Now let's go ahead and memoize this.
And you will note that we just need to add a few lines of code to achieve that.
Now to start with let's create a DP array.
Okay.
So this is going to be a 2D array.
And this will have n rows and w plus one columns.
So let's go ahead and create this 2D array.
Now again let me write this over here.
It will have n rows and w plus one columns.
So I can say const dp is equal to array dot from length n.
Okay, so so far this creates n rows or n elements in the array.
And then each element has to be an array of size w plus one.
So this will ensure that we are creating a 2D DP array.
And over here the size has to be w plus one because we want w plus one columns okay.
And we are also going to fill each of the cells in this 2D dp array with the value minus one.
So that's what we typically do when we write the memoization solution okay.
And again we know that that will help us check over here after the base case whether we have already
computed this or not.
All right.
So so far we have created this DP array.
Now after the base case over here before we go ahead and compute this part, let's first check whether
we had previously computed and stored the value for this particular index and remaining weight.
So we can say if dp at index and remaining weight is not equal to minus one, it would mean that we
already computed and stored this value.
Otherwise it has to be minus one, because we have already filled all the cells in the 2d dp array with
the value minus one.
So if this is not equal to minus one, then we will just return dp at index and remaining weight.
All right.
Now if this is not the case then we proceed.
We calculate exclude and include and then this also goes as it is.
But then before we return this we are going to store it okay.
So we are going to store it over here.
We'll say DP at index.
And remaining weight is equal to what we have over here which is the maximum between exclude and include
and then we will just return DP at index and remaining weight.
So we will return this and that's it.
So notice how with just a few lines of code we were able to memorize the recursive solution.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.