Can anyone help me to come up with a recursion + memorization solution for this problem

link to the problem: https://codeforces.com/contest/1353/problem/E

I have been trying to come up with a recursive + memorization solution please help

I have also tried top to bottom dp state but was unable to understand it as well.

1 Like

Try to think of it not as a DP problem but as maximum subarray sum type problem.

The maximum cost you can incur is equal to total number of 1s in the initial string. (i.e) turning all of them off.

Now for every S[i] at indices 1,1+k,1+2k.… and 2 , 2+k so on, keep a counter.

And update your answer.

yeah! i am late, but might help !!