Problem:- https://atcoder.jp/contests/abc122/tasks/abc122_d

I can't figure out what is wrong with my DP solution.

The DP state dp[i][j][k] represents number of strings of length i with last letters j and k. The letters A,G,C and T are 0,1,2 and 3 respectively. It doesn't work from n=4.

Thank you.

Auto comment: topic has been updated by fiwisr (previous revision, new revision, compare).I don't read your code, but i think 2 last character state is not enough, consider when you want to insert 'C', you need 3 last character to check when the new string is ...A_GC or ...AG_C, for example when n = 4 you will miss this unsatisfied strings: AGGC, AGTC, ATGC.

Thank you. I see my mistake now.

If in case you would like to do it for a larger n you can use matrix exponentiation which gives us a complexity of O(64 * 64 * logn) where 64 x 64 corresponds to a matrix for all possible 3 letter transitions (4^3 as you can fill each position with any of the 4 letters(A, C, G, T)) to all the 3 letter possibilities.

In case if you would like to take a look at the code Solution

Thank you. It is helpful.