在这里插入图片描述
UVA11584
这道题需要两次dp

第一次

定义:$S$为字符串,$IsPalindrome[i][j]$为第$i$个字符到第$j$个字符组成的子串是否为回文$i\leq j$。
初始化

转移方程

如果子串的左边一个字符和其右边一个字符相等,那在这个字串往左右各拓展一格字符形成的新字串仍然时回文串。

第二次

定义:$dp[j]$为前j各字符组成的字串划分成的最小回文串数量。
初始化:$dp[j]=0$
转移方程

1
2
3
4
5
6
7
8
9
10
11
12
for (int j = 1; j <= Len; ++j) {
//将第j个字符看作单独的字串
dp[j] = dp[j - 1] + 1;
for (int i = 1; i < j; ++i) {
//如果i到j是回文串
if (IsPalindrome[i][j]) {
//那i到j看作一个回文串
//dp[j]=前i-1个字符组成的子串能划分的最小数量+1
dp[j] = min(dp[j], dp[i - 1] + 1);
}
}
}

AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[1001];
bool IsPalindrome[1001][1001];
char s[1002];
int Len;
void InitIsPalindrome() {
Len = strlen(s + 1);
memset(IsPalindrome, false, sizeof(IsPalindrome));
for (int i = 1; i <= Len; ++i) {
IsPalindrome[i][i] = true;
IsPalindrome[i - 1][i] = (s[i] == s[i - 1]);
}
for (int j = 2; j <= Len; ++j) {
for (int i = 1; i < j - 1; ++i) {
IsPalindrome[i][j] = IsPalindrome[i + 1][j - 1] && (s[i] == s[j]);
}
}
}
int getAns() {
memset(dp, 0x0, sizeof(dp));
for (int j = 1; j <= Len; ++j) {
dp[j] = dp[j - 1] + 1;
for (int i = 1; i < j; ++i) {
if (IsPalindrome[i][j]) {
dp[j] = min(dp[j], dp[i - 1] + 1);
}
}
}
return dp[Len];
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s + 1,1000);
InitIsPalindrome();
printf("%d\n", getAns());
}
return 0;
}