Problem UVA11584-Partitioning by Palindromes
Accept: 1326 Submit: 7151
Time Limit: 3000 mSec
Problem Description
Input
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.
Output
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
题解：思路很明显，dp[i]的含义是前i个字符组成的字符串所能划分成的最少回文串的个数，定义好这个状态就很简单了，dp[i]肯定是从dp[j]转移过来（j<i）并且需要j+1到i是回文串，此时
dp[i] = min(dp[i], dp[j] + 1)，方程有了，边界也没啥困难的地方。
#include <bits/stdc++.h> using namespace std; const int maxn = + ;
const int INF = 0x3f3f3f3f; char str[maxn]; int is_palindromes[maxn][maxn];
int dp[maxn]; int Is_palindromes(int j, int i) {
if (j >= i) return ;
if (is_palindromes[j][i] != -) return is_palindromes[j][i]; if (str[i] == str[j]) {
return is_palindromes[j][i] = Is_palindromes(j + , i - );
}
else return is_palindromes[j][i] = ;
} int main()
{
//freopen("input.txt", "r", stdin);
int iCase;
scanf("%d", &iCase);
while (iCase--) {
scanf("%s", str + );
memset(is_palindromes, -, sizeof(is_palindromes));
dp[] = ;
int len = strlen(str + );
for (int i = ; i <= len; i++) {
dp[i] = i;
for (int j = ; j < i; j++) {
if (Is_palindromes(j + , i)) dp[i] = min(dp[i], dp[j] + );
}
}
printf("%d\n", dp[len]);
}
return ;
}