Let's now write these space optimized tabulation approach.
So this is the tabulation approach that we had previously written.
And we had used a 2D array.
But as we have discussed in the previous video, we will not be needing this when we go ahead with the
space optimized tabulation approach, we will need two arrays which are of size w plus one.
So let's call them prev and curr okay.
So let prev equal to array.
And the size is going to be w plus one okay.
And we will fill every cell in this array initially with the value zero.
And we will do the same thing with one more array which we can just call curr.
And this also is going to be of size w plus one.
And we will fill every cell in this array with the value zero.
Alright.
Now we proceed over here I takes the value from one up to n and j takes the value from one up to w.
So there is no change over here.
And for exclude wherever we have DPI at I minus one, we replace this with prev.
Okay.
So this is going to be prev at j and initially include is set to zero.
And if weight at I minus one less than equal to j then include is equal to value at I minus one plus
instead of dpi at I minus one.
We will replace this with prev.
So this would be prev at j minus weight at I minus one okay.
And over here we have dpi at I j.
And again we don't have a 2D dpi array over here.
So instead of this we will set this to curve.
So over here we have DPI at I.
And that would be changed to CR.
So whenever we had DPI at I minus one we changed it to prev.
And when we have DPI at I we change it to CR.
So this over here becomes CR at j is equal to math dot max between exclude and include.
And that's it.
Now there's one more thing that we have to do, which is that after going through all the values for
j for a particular value of I that is over here, we will have to set prev two.
What is there in CR at this point?
Okay.
So we can say prev is equal to CR dot slice okay.
So this makes a deep copy.
And then we proceed okay.
And finally over here we are returning DPI at n w.
And instead of DPI at n we'd have to replace this with CR.
And that's it.
So this is the space optimized tabulation approach for solving the zero one knapsack problem.
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.