划分回文数

  试题描述 输入一个小写字母组成的字符串，你的任务是把它划分成尽量少的回文串。例如 racecar 本身就是一个回文串，fastcar只能分成7个单字母的回文串。aaadbccb最少分成3个回文串，aaa,d,bccb.所给字符串长度不会超过1000. 输入 一行，包括符合题目描述的一个字符串。 输出 一个数，表示可分成回文串的最少个数。 输入示例 aaadbccb 输出示例 3

 

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; char a[1010]; int dp[1010]; bool huiwen(int left,int right)//判断划分后是否是回文串 { while(left<right) { if(a[left]!=a[right]) return 0; left++; right--; } return 1; } int main() { int l; scanf("%s",a+1);//输入时让下标从1开始 l=strlen(a+1); for(int i=1;i<=l;i++) { dp[i]=i+1; for(int j=1;j<=i;j++) { if(huiwen(j,i)) dp[i]=min(dp[i],dp[j-1]+1);//dp[i]表示以i结尾的字符串最少可以分割的数量,前者为新字符归到原来的回文字符串，后者为新的字符变为新的字符串。 } } printf("%d",dp[l]); return 0; } View Code

 

转载于:https://www.cnblogs.com/jason2003/p/6572214.html