Welcome back.
We have discussed the memoization approach, which had an O of N into W time and space complexity.
And we have also discussed the tabulation approach, which had a similar time and space complexity,
with the difference that this was an iterative approach and we are not using space on the recursive
call stack.
Now let's go ahead and take a look at how we can optimize the tabulation approach and come up with a
better space complexity for it.
So let's take a look at the space optimized tabulation approach.
So this is the table that we had when we came up with the bottom up approach.
Now let's make some interesting observations over here which will help us to come up with the space
optimized approach.
Notice that whenever we were filling a row, we only needed values that were there in the previous row.
For example, when you were filling this row over here, you only needed the values over here for calculating
the exclude case as well as when you included a value.
You also wanted to understand what extra could be added to the knapsack for both of these.
For calculating the exclude case and the include case, you only needed the previous row.
Now for calculating this.
We never used this nor this.
So this means that we just need to use space for storing the previous row and the current row that we
are computing.
Now let's make use of this insight and optimize the approach that we had taken.
So previously we said that exclude is going to equal to DP at I minus one j and include is going to
equal value at I minus one plus dp at I minus one.
And then whatever the remaining weight that could be added to the knapsack.
Now let's say instead of this DP table we have two 1D arrays.
We can call it previous and cur because we have seen that we just need the previous row to compute the
current row.
Now, instead of dp at I, I will just use the current array and instead of dp at I minus one, I will
just use the previous array which I have over here.
And again the same is applicable over here as well.
And what we will keep doing is like, let's say we are done with computing the values in this array
over here.
So we will set the values over here that were in the current array at this moment to the previous array.
So we will make a copy of this and we will assign it to the previous array.
So in this way we just need to store the previous and current values at a time.
And this would improve the space complexity of the tabulation approach.
Finally the answer is going to be over here.
And that's going to be current at W.
Because again at the end this array over here is going to be there in the current array.
And we just need the last element over here which is going to be current at W.