I'm really sorry if this post sounds stupid, but I'm currently struggling in DP and want to tackle every problem in every possible aspect. The question states that we're given a particular capacity weight W, and we have N items, with ith element having v[i] value and w[i] weight, and we want to maximize the total value we can achieve ( Basically a knapsack problem ). Constraints are as follows,
W <= 1e4;
vi <= 1e9;
wi <= 1e4;
N <= 1e4;
This question can be done, in O(N*W) Time and Space complexity using both top-down and bottom-up approach, and I can further reduce the space to O(2*W) and time O(N*W) using bottom-up approach [link to the bottom-up approach : Link], but I'm unable to think of a similar space-reduced top-down approach. Any intuition behind implementing the "state-reduced" top-down approach will be greatly appreciated.
If you want to reduce space to "O(w*2)" you need to maintain strict order of calculation dp states. First you calculate
dp[0][i](for all i), thendp[1][i], thendp[2][i], etc. That's because dp-formula look likedp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]). Calculatingdp[1][i](for all i) requires information aboutdp[0][j](for all j), and same for otherdp[2][i],dp[3][i], etc. That's the reason why we need only "O(w*2)" space.When you use recursive approach, you can't maintain that strict order of dp states (just like in bottom-up). So, imo, it's impossible.
Thank you for your insight, will keep this in mind for future problems.