题意：给出一个字符串，问最少能划分成多少个回文串
思路：dp题，先预处理出在区间[i, j]内是否能构成回文串，区间[i,j]能构成回文的条件是区间[i+1, j-1]能够成回文，这样的话，设can[i]为以第i个字符结尾最少形成的回文串，则有：
can[i] = min { can[j] + 1 }， 其中区间[j, i]能构成回文
#include<cstdio> #include<cstring> #include<algorithm> const int maxn = 1e3 + 10; const int INF = 1e9; using namespace std; int T; char s[maxn]; int dp[maxn][maxn]; int can[maxn]; int main() { scanf("%d", &T); while(T--) { scanf("%s", s); int len = strlen(s); memset(dp, 0, sizeof dp); for(int i = 0; i < len; i++) { dp[i][i] = 1; can[i] = INF; if(i < len - 1 && s[i] == s[i + 1]) dp[i][i + 1] = 1; else dp[i][i + 1] = 0; } for(int i = len - 1; i >= 0; i--) { for(int j = i + 2; j < len; j++) { if(dp[i + 1][j - 1] && s[i] == s[j]) dp[i][j] = 1; else dp[i][j] = 0; } } can[0] = 1; for(int i = 1; i < len; i++) { if(dp[0][i]) { can[i] = 1; continue; } for(int j = 0; j < i; j++) { if(dp[j + 1][i]) can[i] = min(can[i], can[j] + 1); } } printf("%d\n", can[len - 1]); } return 0; }
