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.