G家老题 Valid String 回答

cpcs

原帖子

string只有可能有A、B、C三个字母组成，如果任何紧邻的三个字母各不相同，那就不是“valid string”。求长度为n的valid string有多少个
- ~' H) A/ l9 H: h" k- n- h8 L1 }比如： ABBBCA不是valid，ACCBCCA是valid
* A: h) b: J  q# W& N/ ~' x8 Z
# g: Y0 [$ Z3 v# C& w
2 E; ?: B' h+ S- s$ t8 H首先我觉得题目应该是紧邻三个字母不全相同吧………………

) d' r5 n. M! g1 `/ ~
dp【i】[0]表示长度为i的合法串，最后两个字符不相等的时候有多少种。
- i# z# S6 A1 k1 j  D8 O/ [0 w$ ]
( p9 z2 e" W5 [( K0 Q5 pdp【i】[1]表示长度为i的合法串，最后两个字符相同的时候有多少种。
$ j3 `7 I  G9 {& E9 r2 Z6 d
: `5 }( }6 X, e* ^) ^* `
  u" o8 x4 z# h4 [; pdp[1][0] = 3
9 `  n6 o8 o3 @4 C5 p% s( mdp[1][1] = 0


考虑下状态转换，根据最后两位的情况可以决定添加哪些字母合法，有：
3 K' v1 X) p$ C" [dp【i】[0] = (dp[i - 1][0] + dp[i - 1][1]) * 2
" d, @* h  B2 _2 fdp【i】[1] = dp[i -1][0]  

& \! D6 t: |5 E
注意dp【i】[0,1]只与dp[i - 1][0,1]有关，于是直接递推，可以滚动数组，把空间复杂度降低为O(1)，时间复杂度为O(n)。


4 O3 h2 o- p4 m7 K有一个O(logn)时间的算法，和求斐波那契数一样：


考虑2 ＊ 2矩阵  
: Q3 G2 K7 `8 K$ i1 O4 [

2    1
( K$ i) v4 E0 k$ E7 [2    0
' n! x/ f6 D5 O  Z) R6 @
- i' O8 ?% K3 Z; b( q1 E
1 ＊ 2 的的向量 (dp[i - 1][0], dp[i - 1][1]) 乘以上个矩阵，就会得到(dp【i】[0], dp【i】[1])，于是问题转化为求那个矩阵的(n - 1)次方，这个有经典的求幂算法——powermod，时间复杂度O(logn)，空间复杂度O(1)。

9 ~" C# p/ b( D" \( M  g
最后结果 dp[n][0] + dp[n][1]
) ?3 K2 C0 ~) y- \! z3 |! L, I
$ w! m$ V9 i! U来源: G家老题 Valid String 回答

caowang888

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

sunnyday

It's a good problem!