### Mohd__Messi's blog

By Mohd__Messi, history, 9 days ago,

• +1

 » 9 days ago, # | ← Rev. 3 →   0 It's pretty much Knapsack DP.I will mention the dynamics:$dp_{i,j,0}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ <=j\ and\ operation\ is not\ used.$$dp_{i,j,1}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ <=j\ and\ operation\ is\ used.$$Transitions\ are\ similar\ to\ Knapsack\ DP.$Your answer will be $max(dp[n][m][0]\ ,\ dp[n][m][1])$My solution: https://ideone.com/NgqsT4
•  » » 9 days ago, # ^ |   0 Brother please can you clear my doubt I use 3 dp states dp[n][m][flag] The code passed the test cases but when I was using 2 dp states dp[n][m] and was updating the value for flag . Then it was failing on few cases why is so???This is my previous code:- https://pastebin.com/E1hqm56HThis is new code:- https://pastebin.com/xEqn2Uq8
•  » » » 9 days ago, # ^ |   0 The problem is with the statement if(dp[n][m]!=-1) return dp[n][m]; , since we don't know if flag was true or false, in the returned state,so it may lead to overcount.
•  » » » » 9 days ago, # ^ |   +1 Thanks I understood my mistake
 » 9 days ago, # | ← Rev. 2 →   0 I did in recursive way with Memoization...I also made choices in that recursion part..! Click Here — My Submission — This problem is pretty similar to knapsack one just here,there is one more case.. You can check the submission I did with comments
•  » » 9 days ago, # ^ |   0 Bro I can't see your sub plz share it through paste bin or ideone
•  » » 9 days ago, # ^ |   0 Brother please can you clear my doubt I use 3 dp states dp[n][m][flag] The code passed the test cases but when I was using 2 dp states dp[n][m] and was updating the value for flag . Then it was failing on few cases why is so???This is my previous code:- https://pastebin.com/E1hqm56HThis is new code:- https://pastebin.com/xEqn2Uq8
 » 9 days ago, # |   0 Using memoization. Code