mb640163eb338d0 2023-03-03 14:00:23 博主文章分类：----------DP ©著作权

文章标签 字符串 递推 时间复杂度 文章分类 Python 后端开发

字符串只有可能有A、B、C三个字母组成，如果任何紧邻的三个字母相同，就非法。求长度为n的合法字符串有多少个？比如： ABBBCA是非法，ACCBCCA是合法的。

动态规划的思路——真的要枚举么？ dp[i][0] : 长度为i的、最后两位不同的合法串的个数 dp[i][1]: 长度为 i的、最后两位相同的合法串的个数 递推: dp[i][0] = (dp[i-1][0] * 2 + dp[i-1][1] * 2) dp[i][1] = dp[i-1][0]

初值 dp[1][0] = 3, dp[1][1] = 0 结果 dp[n][0] + dp[n][1] 空间优化 dp[i][0,1]只与dp[i-1][0,1]相关，可以省掉高维 时间复杂度 O(n)

上一篇：LightOJ 1422 Halloween Costumes 【区间DP】

下一篇：poj 2955 Brackets【区间DP】