题目链接：https://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=307682
无从下手的时候考虑DP……
区间DP考虑优化成线性DP……
统计回文串，可以枚举中点，想两边扩展……
预处理出以每个字符为结尾的最长回文串，记录其起点；对于每一个字符来说，枚举以这个字符为终点的回文串，选最小值。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> using namespace std; const int maxn = 5000 + 10; const int INF = (1<<31)-1; char a[maxn]; int f[maxn]; bool s[maxn][maxn]; vector<int> prv[maxn]; bool check(int s, int t){ for (int i=s; i<=(s+t)/2; i++){ if (a[i] != a[s+t-i]){ return false; } } return true; } int main() { scanf("%s", a); int len = strlen(a); for (int i=0; i<len; i++){ //预处理长度为奇数的回文串 int l = i; int r = i; while (l >= 0 && r < len && a[l] == a[r]){ prv[r].push_back(l); l--; r++; } } for (int i=0; i<len; i++){ //预处理长度为偶数的回文串 int l = i; int r = i + 1; while (l >= 0 && r < len && a[l] == a[r]){ prv[r].push_back(l); l--; r++; } } f[0] = 1; //线性DP for (int i=1; i<len; i++){ f[i] = INF; for (int k=0; k<prv[i].size(); k++){ f[i] = min(f[i], f[prv[i][k]-1]+1); } } cout << f[len-1] << endl; return 0; }