bro in your code when setting values of dp for first 3 elements why you didn’t chose the min ones. You just iterated for possible combinations of i+j+k%3==0 and just set the dp value to ch(a[0],i)+ch(a[1],j)+ch(a[2],k) wouldn’t we want to set this value to minimum.
I checked all those states the same reason why this editorial bruteforced for all 3^2 possible starting points. It is possible the optimal solution might start from ANY of those combinations and NOT just the ones that give immediate minimum answer. If it always did, then there is no point using dp and we could have just done greedy in O(N) time complexity.
If you mean, why i didn’t set all those states to the minimum of all those states. That would be simply incorrect and not follow the dp statement i made in the explanation. I’ve updated the dp statement to make it easier to understand.
I also now tried without dp finally got it accepted . logic was like what was explained in the editorial . below is the code if anyone needs. https://www.codechef.com/viewsolution/100869962 . will try dp based approach too later .
Oh ok got it thanks!!
bro in your code when setting values of dp for first 3 elements why you didn’t chose the min ones.