题意：输入一个有小写字母组成的字符串，你的任务是将它划分成尽量少的回文串
思路：dp[i]代表到第i位的最小值，枚举它的前几位求出最小值，为了方便枚举整个长度我们 从str[1]开始输入
#include#include #include #include using namespace std; const int MAXN = 2000; char str[MAXN]; int dp[MAXN]; int check(int l,int r){ int flag = 1; for (int i = 0; i < (r-l)/2+1; i++) if (str[l+i] != str[r-i]){ flag = 0; break; } return flag; } int main(){ int t; scanf("%d",&t); while (t--){ str[0] = '0'; scanf("%s",str+1); dp[0] = 0; int len = strlen(str) - 1; for (int i = 1; i <= len; i++){ int Min = 0x3f3f3f3f,temp; for (int j = 0; j < i; j++){ if (check(j+1,i)) temp = dp[j] + 1; else temp = dp[j] + i - j; Min = min(Min,temp); } dp[i] = Min; } printf("%d\n",dp[len]); } return 0; }