题目描述
给一个字符串， 要求把它分割成若干个子串，使得每个子串都是回文串。问最少可以分割成多少个。 字符串长度不超过1000。
例如：
“racecar”本身就是回文串，答案为1
“fastcar”，答案为7，分成的7个回文串为"f", "a", "s", "t", "c", "a", "r"
“aaadbccb”,答案为3，分成的3个回文串为"aaa", "d", "bccb"
输入
第一行一个数T。接下来T行，每行一个字符串。
输出
对于每个字符串输出答案。
样例输入
3
racecar
fastcar
aaadbccb
样例输出
1
7
3
题解
dp[i] 为字符串中 1~i 划分成最少回文串的个数。则：
dp[ i ]=min( dp[ j ] + 1 ) 其中，s[ j+1 -> i ] 为回文串
于是我们发现时间复杂度来到了O(n3)，不够优秀。考虑降低复杂度，我们用O(n2)的时间预处理出 s[ i --> j ] 是否为回文串
然后总时间复杂度降为 O(n2)。
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=1000+10; char a[maxn]; int dp[maxn],l,lef,rig; bool p[maxn][maxn]; template<typename T>void read(T& aa) { char cc; ll ff;aa=0;cc=getchar();ff=1; while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar(); if(cc==‘-‘) ff=-1,cc=getchar(); while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar(); aa*=ff; } int main(){ memset(dp,127,sizeof(dp)); memset(p,false,sizeof(p)); scanf("%s",a+1); l=strlen(a+1); for(int i=1;i<=l;i++){ lef=i;rig=i; while(lef>0&&rig<=l){ if(a[lef]==a[rig]) p[lef][rig]=true; else break; lef--;rig++; } } for(int i=1;i<l;i++){ lef=i;rig=i+1; while(lef>0&&rig<=l){ if(a[lef]==a[rig]) p[lef][rig]=true; else break; lef--;rig++; } } dp[1]=1;dp[0]=0; for(int i=2;i<=l;i++) for(int j=0;j<i;j++){ if(p[j+1][i]) dp[i]=min(dp[i],dp[j]+1); } cout<<dp[l]<<endl; return 0; }
原文：https://www.cnblogs.com/rlddd/p/9495314.html