Alice and Bob Problem DP

#1

Ques : https://hack.codingblocks.com/contests/c/452/1013
Please explain its solution with DP. what does dp[] represent in the solution

#2

You have 2 options for each element:

  1. whether you will pick all occurences of element with value i, leave element with value (i-1) and all its occurences.
  2. Pick elements with value i-1.

So here dp comes into play.

1 Like
#3

https://ide.codingblocks.com/s/46945

Here is my solution for your reference. Do let me know in case of any issues.

1 Like
#4

it is failing bro
in some test cases