Welcome back.
So we have discussed how to solve the unbounded knapsack problem using the tabulation approach.
Now this is the DP table that we used for it.
And again remember what we did was we went through all of these cells.
And then finally once we are done computing the value for this cell, we would return that because that
gives us the answer.
Now what would be the time complexity of this approach?
The time complexity for this is going to be of the order of n into W, because we have N into W cells
over here, and we would go through each of these cells to compute their value.
And for computing the value for each cell we would just do constant time operations.
Right.
So that's why the total time complexity for coming up with the answer using this approach is going to
be of the order of n into w.
Now what about the space complexity?
Again, the space complexity of this solution is also of the order of n into w, because we are using
this DP table over here, which takes up space of the order of n into W, because we have n plus one
rows and w plus one columns.
Now you can optimize this and you can get a space complexity which is of the order of W.
And for that you just need to follow the same approach that we discussed.
When we discuss the zero one knapsack problem to come up with the space optimized tabulation approach.
So go ahead and give it a try and try to do that on your own.