Hrdv is interested in a string,especially the palindrome string.So he wants some palindrome string.A sequence of characters is a palindrome if it is the same written forwards and backwards. For example, 'abeba' is a palindrome, but 'abcd' is not.A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, ('race', 'car') is a partition of 'racecar' into two groups.Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome?For example:'racecar' is already a palindrome, therefore it can be partitioned into one group.'fastcar' does not contain any non-trivial palindromes, so it must be partitioned as ('f', 'a', 's', 't', 'c', 'a', 'r').'aaadbccb' can be partitioned as ('aaa', 'd', 'bccb').Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes

racecar

fastcar

aaadbccb

1

7

3

 

使用dp（i）表示从数组起始位置到i位置回文串的个数

动态规划方程为

dp(i)=min{dp(j-1)+1,dp[i]}  //if(子串j~i是回文串)

初始给dp赋值为一个大数，代表这个区间的回文串个数未知

#include"iostream"#include"cstdio"#include"cstring"#include"algorithm"using namespace std;const int maxn=1010;char aa[maxn];int dp[maxn];bool is_palindrome(int a,int b){    int m=(a+b)>>1;    for(int i=a; i<=m; i++)        if(aa[i]!=aa[b-i+a]) return false;    return true;}int main(){    int T;    cin>>T;    while(T--)    {      scanf("%s",aa+1);      int n=strlen(aa+1);      memset(dp,0,sizeof(dp));      dp[0]=0;    for(int i=1;i<=n+1;i++) dp[i]=n;    for(int i=1;i<=n;i++)    for(int j=1;j<=i;j++)      {        if(is_palindrome(j,i))          //dp[i]=dp[j-1]+1;            dp[i]=min(dp[i],dp[j-1]+1);      }      cout<
       
        <