Makise_Kurisu's blog

Need Help in GCD Partitions [Dynamic Programming]
By Makise_Kurisu, 4 years ago, In English

Hi, I was trying to solve this problem. And after going through a couple of submissions (Here is a neat one) I got the transition recurrence but I am still not able to work around the intuition behind it. Can someone please explain a little about what are the pointers which lead you this recurrence and also I am sorry if it's a standard dp type(if possible please share some resource or problem based on the same idea :P)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Let

$$$f(i, j) = \text{maximum sum if we partition the first i elements in j parts}$$$

Then the answer is clearly f(n, k). The recurrence relation is

$$$f(i, j) = \displaystyle\max_{k < i}f(k, j-1) + \text{GCD}(a[k+1], \dots, a[i])$$$

with the base case being f(i, 1) = GCD(a[1],..,a[i]).

You can find my implementation here.

The trick about such DP problems is to think of the right states. Then the recurrence will be pretty obvious. This, however, needs some practice. If I recall correctly, in the book Competitive Programming 3 there is a note in the Dynamic Programming chapter where the authors present some common states in DP problems. With enough practice you should be able to find the correct states more often.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for such a great explanation. Highly appreciate it!

    → Reply