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.
Full text and comments »