题目链接：
https://cn.vjudge.net/problem/34398/origin
本题的大意其实很简单，就是找回文串，大致的思路如下：
1. 确定一个回文串，这里用到了自定义的check函数原理如下：
传入le, ri两个值（定义从1开始）, s+1 = aaadbccb.
a a a d b c c b
1 2 3 4 5 6 7 8
比如，le = 5, ri = 8. 则s[5] == s[8]成立
le++ ri--
再比较 s[6] == s[7]? 成立
le++, ri--. 此时， le > ri return true.
所以，这就是一个字符串。
2. 动态dp
定义个f[MX]函数用于动态dp
首先初始化f[n] = n;
然后check(j. i);
如果返回成true则进行动态规划 f[i] = min(f[i], f[j-1]+1)
3. 输出f[n]即可
下面是AC代码：
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int MX = 1000+10; char s[MX]; int f[MX]; bool check(int le, int ri) { while(le <= ri) { if(s[le] != s[ri]) return false; le++; ri--; } return true; } int main() { int T; scanf("%d", &T); while(T--) { memset(f, 0, sizeof(f)); scanf("%s", s+1); //从第二位，也就是1开始填字符 int n = strlen(s+1); //计算s+1的长度 for(int i = 1; i <= n; ++i) //动态dp { f[i] = i; //初始化，每个均为一 for(int j = i; j > 0; j--) { if(check(j, i)) f[i] = min(f[i], f[j-1]+1); } } printf("%d\n", f[n]); } }
原文：https://www.cnblogs.com/mpeter/p/10292086.html
