欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

回声字符串(动态编程解决方案)

最编程 2024-06-07 22:57:37
...
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 char s[1002];
6 int f[1001][1001];
7 int main()
8 {
9 int tcases, n, i, j;
10 cin >> tcases;
11 while(tcases--)
12 {
13 scanf("%s", s);
14 n = strlen(s);
15 memset(f, 0, sizeof(f));
16 for(i = 0; i < n; i++)
17 {
18 f[0][i] = 0;
19 f[1][i] = 0;
20 }
21 for(i = 2; i <= n; i++)
22 for(j = 0; j < n; j++)
23 {
24 if(s[j] == s[i+j-1])
25 {
26 f[i][j] = f[i-2][j+1];
27 }
28 else if(f[i-1][j] < f[i-1][j+1])
29 {
30 f[i][j] = f[i-1][j] + 1;
31 }
32 else f[i][j] = f[i-1][j+1] + 1;
33 }
34 printf("%d\n", f[n][0]);
35 }
36 return 0;
37 }

推荐阅读