Link：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1154
#include <bits/stdc++.h> using namespace std; /* 题意：有一个字符串S，求S最少可以被划分为多少个回文串。 题解：暴力预处理出每位能到达范围，dp可以由当前处理位置选择多长回文串转移。 */ const int N = 5005; const int INF = 0x3f3f3f3f; int ma[N],mb[N],len; char s[N]; void Ma(int x){ int i = 1; while(x-i>=1 && x+i<=len && s[x+i] == s[x-i]) i++; ma[x] = i-1; //两边ma[i] } void Mb(int x){ int i = 1; while(x-i+1>=1 && x+i<=len && s[x-i+1] == s[x+i]) i++; mb[x] = i-1; //左边mb[i]-1,右边mb[i] } int dp[N]; //处理到i为中心的回文串 的最小划分数 int main(){ scanf("%s",s+1); len = strlen(s+1); //printf("%d\n",len); for(int i = 1; i <= len; i++){ Ma(i); Mb(i); dp[i] = i; } dp[0] = 0; for(int i = 1; i <= len; i++){ for(int j = 0; j <= ma[i]; j++) dp[i+j] = min(dp[i+j],dp[i-j-1]+1); for(int j = 1; j <= mb[i]; j++) dp[i+j] = min(dp[i+j],dp[i-j]+1); } // for(int i = 1; i <= len; i++) // printf("%d\n",dp[i]); printf("%d\n",dp[len]); return 0; }