d[i]表示从1~i位最小回文子串数（下标按从1开始），d[i]=min(d[i],d[j]+1|j+1到i为回文串)。 正确性证明：考虑添加第i位字母，有两种情况： 1.第i位自成一回文串。 2.第j+1位到第i位为一回文串。 枚举所有1、2情况即可求得d[i]。
#include<iostream> #include<cstring> using namespace std; int n,d[1005]; bool p[1005][1005]; int main() { string s; cin>>n; for(int i=1;i<=n;i++) { cin>>s; int l=s.length(); for(int j=0;j<l;j++) { for(int k=0;k<=l;k++) if(s[j+k]==s[j-k]&&j+k<l&&j-k>=0) p[j-k+1][j+k+1]=1; else break; } for(int j=0;j<l-1;j++) if(s[j]==s[j+1]) for(int k=0;k<=l;k++) if(s[j-k]==s[j+1+k]&&j-k>=0&&j+1+k<l) p[j-k+1][j+k+2]=1; else break; memset(d,0x3f3f3f,sizeof(d)); d[0]=0; for(int j=1;j<=l;j++) for(int k=1;k<=j;k++) if(p[k][j]) d[j]=min(d[j],d[k-1]+1); cout<<d[l]<<endl; memset(p,0,sizeof(p)); } return 0; }