p1125 [noip2008 提高组] 笨小猴

题目描述：

笨小猴在玩耍，它有一个长度为 n 的字符串 s。它想把这个字符串切成若干个非空的子串，使得每个子串都是回文串。它最少需要切几刀？

输入格式：

输入共一行，为一个长度为 n 的字符串 s。

输出格式：

输出共一行，为一个整数，表示最少需要切的刀数。

数据范围：

1≤n≤500

输入样例：

aab

输出样例：

1

算法1

(动态规划) $O(n^2)$

1.状态表示
dp[i]表示前i个字符最少可以分成几个回文串

2.状态转移
dp[i] = min(dp[j] + 1) (j < i && j + 1 ~ i是回文串)

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(中心扩展) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码