本题是一道非常经典的动态规划题目。
设S[1..n]是一个长度为n的字符串,best(S)是S的最短压缩,那么best(S)可能为三种形式中最短的一种:
1) 原串形式:best(S) = S。例如CCD最短压缩就是CCD本身。
2) 拼接形式: best(S[1..n]) = best(S[1..i]) + best(S[i+1..n])。
例如AAAAAAAAAABABABCCD的最短压缩9(A)3(AB)CCD,可以视为由best(AAAAAAAAAABABAB) = 9(A)3(AB) 和 best(CCD) = CCD 拼接而成。
3) 嵌套形式: best(S[1..n]) = k的位数 + 2 + best(S[1..n/k]),其中k>1且是n的约数,S是由k个S[1..n/k]循环拼接而成。
也就是说S[1..n]可以表示成k(s[1..n/k]),这时k(s[1..n/k])的长度是k的位数 + 一对括号的长度2 + best(S[1..n/k)
例如HIHOHIHOCODERHIHOHIHOCODER有循环节HIHOHIHOCODER,所以best(HIHOHIHOCODERHIHOHIHOCODER) = 1 + 2 + (best(HIHOHIHOCODER))。
思路清晰,腻害了大兄弟