G家老题 Valid String 回答

cpcs

原帖子

) A0 A9 v0 ^1 m; l1 |. _string只有可能有A、B、C三个字母组成，如果任何紧邻的三个字母各不相同，那就不是“valid string”。求长度为n的valid string有多少个
# g( }" T) l' Q. U2 E; B比如： ABBBCA不是valid，ACCBCCA是valid
/ z- _) k* z, U6 W# P; A8 o/ q

1 R1 @( a! W# O# U首先我觉得题目应该是紧邻三个字母不全相同吧………………


dp【i】[0]表示长度为i的合法串，最后两个字符不相等的时候有多少种。
' {! ]: ?- j0 P7 h
dp【i】[1]表示长度为i的合法串，最后两个字符相同的时候有多少种。
0 f7 J) Q7 P9 V
  z- m9 Q" k1 t$ [+ |$ m
2 z# R* f' q3 B4 x/ a0 }dp[1][0] = 3
- _) C6 a) u* q# B" x: D3 pdp[1][1] = 0

( M7 x6 R  l9 b9 y; J) U7 b
考虑下状态转换，根据最后两位的情况可以决定添加哪些字母合法，有：
dp【i】[0] = (dp[i - 1][0] + dp[i - 1][1]) * 2
; L: ^7 t2 r9 G  O1 l, s4 J. Ldp【i】[1] = dp[i -1][0]  
2 A8 t, G" r3 e6 X$ V

注意dp【i】[0,1]只与dp[i - 1][0,1]有关，于是直接递推，可以滚动数组，把空间复杂度降低为O(1)，时间复杂度为O(n)。
0 D/ E, _" r; n+ d# j+ X2 u) v) |

5 f$ V/ k, }/ [; l有一个O(logn)时间的算法，和求斐波那契数一样：


. r5 _6 D' r( [' Z+ x考虑2 ＊ 2矩阵  
' }, @* Z& I) L/ C

2    1
* }- I* C0 g3 M2    0

" m9 k: k8 X" T$ {4 I# X
1 ＊ 2 的的向量 (dp[i - 1][0], dp[i - 1][1]) 乘以上个矩阵，就会得到(dp【i】[0], dp【i】[1])，于是问题转化为求那个矩阵的(n - 1)次方，这个有经典的求幂算法——powermod，时间复杂度O(logn)，空间复杂度O(1)。
" Y- K' a2 W' {; }7 J# y

8 O0 l' @0 e( l) S8 ~) p" c. m最后结果 dp[n][0] + dp[n][1]

7 r6 A* v/ I; {" s来源: G家老题 Valid String 回答

caowang888

赞，受益匪浅！之前知道DP，但是不知道转化成矩阵相乘和powermod。

sunnyday

It's a good problem!