Mohd__Messi's blog

By Mohd__Messi, history, 9 days ago, In English
 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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/E1hqm56H

    This is new code:- https://pastebin.com/xEqn2Uq8

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Using memoization. Code