themaskedhero's blog

By themaskedhero, history, 3 years ago, In English,

Hi everyone,

I was solving this problem and I was unable to. I believe that this is DP, but I do not know the state. I do note that, for any gum, we can easily uniquely determine how much it will cost to take n teeth from that gum by picking greedily.

Thanks much in advance, themaskedhero

  • Vote: I like it
  • +4
  • Vote: I do not like it

3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I liked this problem, it's indeed solved using DP. That was my approach to it:

State of the DP

Basically a dp[ current_gum ][ number_of_cured_teeth ].

I filled the DP from left to right, top to bottom. For each gum you find the price of curing x teeth using the accumulated result of previous gum.

That runs in O(N*K).

Keeping track of cured teeth

To pass the time limit you must keep track of cured teeth in O(1). Adding a third dimension on the DP, with only 3 values, proved itself helpful.


I something wasn't clear you can check the code I used, it has a lot of comments: Don't click me.