本文共 970 字，大约阅读时间需要 3 分钟。
题意：给一个字符串， 要求把它分割成若干个子串，使得每个子串都是回文串。问最少可以分割成多少个。
分析：dp[i] 为字符0~i划分的最小回文串的个数，则dp[i]=min(dp[i],dp[j]+1|s[j+1~i]为回文串)。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #define ll long long#define mod 1000000007#define mem(a) memset(a,0,sizeof(a))using namespace std;const int maxn = 1000 + 5 , inf = 0x3f3f3f3f ;char s[maxn];int dp[maxn];bool vis[maxn][maxn];bool can(char *s,int L,int R){ int RR = R; int LL = L; while(RR>=LL){ if(s[RR--]!=s[LL++]) return false; } return true;}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); int n; scanf("%d",&n); while(n--){ mem(dp); scanf("%s",s+1); mem(vis); int len = strlen(s+1); for(int i=1;i<=len;i++){ dp[i]=i+1; for(int j=1;j<=i;j++){ if(can(s,j,i)) dp[i]=min(dp[i],dp[j-1]+1); } } cout< <
转载于:https://www.cnblogs.com/seven7777777/p/10278728.html