Need Help in GCD Partitions [Dynamic Programming]

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) @everule1

1 Like

I can understand your problem. I would recommend you to have a look at the recursive solution for a better understanding.

Let me explain the approach :

In our recursive function we pass two parameters (i, k) and dp(i, k) means the maximal sum obtained from [i:n] where i is on the k - th partition.

We loop through every element starting from i, keep gcd-ing the value and for every index check the result of the next index.

Let us take an array [2, 4, 5 ,3 ,6] and K = 3

Following is a vivid description of the recursion. You can simply memorize the (i, k) states and get an accepted solution. :slight_smile:

Check out the diagram



Thanks for such a detailed explanation. This was exactly what I was looking for. I Highly appreciate it.

1 Like

Thanks! Glad I could help. :grin: