### fiwisr's blog

By fiwisr, history, 7 months ago, ,

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

https://p.ip.fi/dn_u

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.

• +6

 » 7 months ago, # |   0 Auto comment: topic has been updated by fiwisr (previous revision, new revision, compare).
 » 7 months ago, # |   +8 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.
•  » » 7 months ago, # ^ |   +3 Thank you. I see my mistake now.
 » 7 months ago, # |   +3 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
•  » » 7 months ago, # ^ |   +3 Thank you. It is helpful.