1.题目描述：点击打开链接
2.解题思路：本题要求划分回文串，，且个数尽可能的少。可以用动态规划解决。先提前判断i~j是否构成回文串，时间复杂度是O(N^2)，然后定义d(i)表示0~i-1划分成的回文串的最小个数。则状态转移方程为：
d(i)=min(d(i),d(j)+1)(s[j…i]是回文串)
上式中，d(i)的初始值是i,这样每次判断只需要O(1)的时间，总时间复杂度是O(N^2)。当然，判断回文串的过程可以和状态转移相结合，细节请参考第二份代码。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define maxn 1030000int vis[maxn];int d[maxn];int n;int main(){//freopen("test.txt", "r", stdin);cin >> n;while (n–){string str;cin >> str;memset(vis, 0, sizeof(vis));memset(d, 0, sizeof(d));int len = str.length();for (int i = 0; i <= len; i++)d[i] = i;for (int i = 0; i < 2 * len – 1; i++)//枚举中心，判断i到j是否为回文串{int p;int m = i / 2;for (int j = m; j >=0; j–){if (i – j<len&&str[j] == str[i – j]){p = (j << 10) | (i – j);vis[p] = 1;}else break;}}int q = 0;for (int i = 0; i <= len; i++)//枚举起点，终点{for (int j = 0; j <= i – 1; j++){q = (j << 10) | (i – 1);if (vis[q])d[i] = min(d[i], d[j] + 1);}}printf("%d\n", d[len]);}return 0;}
参考代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1002int f[N];bool d[N][N];int main(){freopen("test.txt","r", stdin);int n, t, i, j, result;cin >> t;while (t–){string s;cin >> s;n = s.length();memset(f, 1000000, sizeof(f));memset(d, false, sizeof(d));for (int i = 0; i <= n; i++)//f[i]表示i到n划分成的最小回文串的个数f[i] = n – i;for (int i = n – 1; i >= 0; i–)//i是起点，逆序枚举for (int j = i; j < n; j++)//j是终点，顺序枚举if (s[i] == s[j] && (j – i < 2 || d[i + 1][j – 1])) //如果j-i<2那么只需要直接用s[i]==s[j]判断即可，否则，用d[i+1][j-1]来判断是否为回文串{d[i][j] = true;f[i] = min(f[i], f[j + 1] + 1);}cout << f[0] << endl;}return 0;}
一个有信念者所开发出的力量，大于99个只有兴趣者。
