|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
本帖最后由 Sophia 于 2-17-2016 04:53 PM 编辑 - _" G; k8 a9 K0 q& | Z: W
5 ^/ `0 D. K, T9 ^% u; t) }
原帖子7 e; ?% O0 M9 L
, @& P ^; i5 P# W) |
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首先我觉得题目应该是紧邻三个字母不全相同吧………………: h. S* J5 b7 }5 O# \
) d' r5 n. M! g1 `/ ~0 N7 P/ x5 w% u; V6 \3 J
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, z9 K4 w6 p. y
, g, J5 T' v3 l: f; }
; D' p# `: j6 }
考虑下状态转换,根据最后两位的情况可以决定添加哪些字母合法,有:
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] 7 D w- s0 f. F
& \! D6 t: |5 E9 Q2 e, S" p! z6 R" _" u
注意dp【i】[0,1]只与dp[i - 1][0,1]有关,于是直接递推,可以滚动数组,把空间复杂度降低为O(1),时间复杂度为O(n)。 l& s4 V, o0 A. T: H w& V) U2 ~
: H& s) U, N# [1 h. W, U! t) b$ C
4 O3 h2 o- p4 m7 K有一个O(logn)时间的算法,和求斐波那契数一样:) O% J: y1 r! _ m. [; W$ b
0 N1 c% W- V X/ r5 N3 B( s
/ l/ p+ T& f3 W( |
考虑2 * 2矩阵
: Q3 G2 K7 `8 K$ i1 O4 [4 | {8 u% n: @& D; c4 m' B/ P
( C" C2 c" p# u) h7 [' ?
2 1
( K$ i) v4 E0 k$ E7 [2 0
' n! x/ f6 D5 O Z) R6 @
- i' O8 ?% K3 Z; b( q1 E" {& X, F7 c) | B) H! M1 V3 a
1 * 2 的的向量 (dp[i - 1][0], dp[i - 1][1]) 乘以上个矩阵,就会得到(dp【i】[0], dp【i】[1]),于是问题转化为求那个矩阵的(n - 1)次方,这个有经典的求幂算法——powermod,时间复杂度O(logn),空间复杂度O(1)。7 Y3 c M, x6 I: C' g. H& j- B
9 ~" C# p/ b( D" \( M g- J+ ?4 o! V0 c. L. v, K8 k
最后结果 dp[n][0] + dp[n][1]
) ?3 K2 C0 ~) y- \! z3 |! L, I
$ w! m$ V9 i! U来源: G家老题 Valid String 回答 |
|