We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, 'racecar' is a palindrome, but 'fastcar' 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.
For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.
Sample Input
3 racecar fastcar aaadbccb
Sample Output
1 7 3题意：给定一个字符串，求最少可以分成几个回文字符串 思路：先预处理出所有字串是否是字符串。用o(n^2)的方法，然后就是dp，如果str[i,j]这个字符串是回文串，那么dp[i] = min(dp[i], dp[j - 1] + 1)，总复杂度o(n^2) 代码：
#include#include #define INF 0x3f3f3f3f #define min(a,b) ((a)<(b) (a):(b)) const int N = 1005; int t, n, dp[N], ok[N][N]; char str[N]; void init() {//预处理 for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) { if (i == j || (str[i] == str[j] && (ok[j + 1][i - 1] || i - j == 1))) ok[j][i] = 1; else ok[j][i] = 0; } } int solve() { memset(dp, INF, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) { if (ok[j][i]) { dp[i] = min(dp[i], dp[j - 1] + 1); } } return dp[n]; } int main() { scanf("%d", &t); while (t--) { scanf("%s", str + 1); n = strlen(str + 1); init(); printf("%d\n", solve()); } return 0; }