I have just started understanding Dynamic programming. And so after some reading, and understanding some basic sums (knapsack, common sub-sequence, etc ), I went to solve these:
Knapsack 1 and Knapsack 2
I could solve the first one. But wasn't quite able to understand the 2nd one. got me somewhere. could you please solve these few doubts of mine?
- Was a different approach used just because of the space complexity of the DP matrix?
- These sums gave two definitions of dp table for knapsack. i.) max profit possible till that perfect weight. ii.) min weight required to get that much profit. so for sums NOT lying in the extremities, both of these solutions will give a correct answer? Any other input is appreciated. It's a bit complicated to get my head around DP.
In Dynamic Programming Problems there are some parameters which determine the state of the problem. For eg in Knapsack Problem There are 3 parameters for any state i.e where you are currently (at which index), how much Weight of knapsack you have and what value (maximum in most cases or based on any other property ) you can get. In some problems some constraints for some parameter for which we use DP table are kept very big therefore we need to use some other parameter and we try to derive our answer from that. Notice the constraints for value and think that if we can find minimum weight that we need to get any value than we will have to find the highest value for which minimum weight is less than our knapsack weight (It means we can get that value with our knapsack). You can have a look at my solution for reference https://atcoder.jp/contests/dp/submissions/12183786
This course has well detailed video editorials to first 5 problems of the Atcoder dp contest made by me. You can try the video solutions to knapsack 1 and Knapsack 2, i have tried to explain the solutions in the best way possible.
Also the course is currently free of cost. Do give it a try :)
I watched them sometime ago! Well done!!
Thankyou :)