感觉没问题啊
复杂度是$O(N^2)$

#include<iostream>
#include<cstring>
using namespace std;
int n,len,boos[1010][1010],d[1010];
string s;
int pd(void);
void cmp(int,int);
int main()
{
    cin>>n;
    while(n--)
    {
        memset(d,0x3f3f3f3f,sizeof d); d[0]=1;
        memset(boos,0,sizeof boos);
        cin>>s;
        len=s.size();
        pd();
        for(int i=0;i<len;i++)
        {
            for(int j=-1;j<i;j++)
            if(j==-1) { if(boos[0][i]) d[i]=1;}
            else if(boos[j+1][i]) d[i]=min(d[j]+1,d[i]);
        }
        cout<<d[len-1]<<endl;
    }
    return 0;
}
int pd(void)
{
    for(int i=0;i<len;i++)
    {
        cmp(i,i);
        if(i+1<len) cmp(i,i+1);
    }
}
void cmp(int a,int b)
{
    if(a<0||b>=len) return;
    if(s[a]==s[b])
    {
        boos[a][b]=1;
        cmp(a-1,b+1);
    }   
    return;
}