|
题意：给出一个字符串，可以添加删除字符，或替换字符，求把它变成回文的最少操作次数。
可以用递推或者递归，其实递归更好理解，递推还要确定滚动方向。
dp[i][j]表示字符i到j位置上最少需要几步构成回文。
dp方法为：如果str[i] = str[j]，dp[i][j]=dp[i + 1][j - 1]; 否则dp[i][j] = min(dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1]) + 1
由于定义min是没括上括号，调了老旧 - -
代码：
|
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 |
#include <cstdio>
#include <cstring>
#define min(a, b) ((a) < (b) ? (a) : (b))
const int MAXN = 1010;
int dp[MAXN][MAXN];
char ch[MAXN];
int t, cas;
int main() {
scanf("%d", &t);
for (cas = 1; cas <= t; cas++) {
scanf("%s", ch);
int len = strlen(ch);
for (int i = 0; i < len; i++)
dp[i][i] = 0;
for (int i = len - 1; i >= 0; i--)
for (int j = i + 1; j < len; j++)
if (ch[i] == ch[j])
dp[i][j] = dp[i + 1][j - 1];
else
dp[i][j] = min(min(dp[i + 1][j], dp[i + 1][j - 1]), dp[i][j - 1]) + 1;
printf("Case %d: %d\n", cas, dp[0][len - 1]);
}
return 0;
|
|
