引用大牛lnmm的思路
设ch[1]..ch[n]表示字符串1至n位，i为左游标，j为右游标 ，则i从n递减，j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n]. 则
if(ch[i]==ch[j]) //如果两个游标所指字符相同，向中间缩小范围
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 + （min[i+1][j]和min[i][j-1]中的较小值）; //如果不同，典型的状态转换方程
画个图
1 | i\j 1 2 3 4 5 |
2 | 1 0 * * * * |
3 | 2 0 0 * * * |
4 | 3 0 0 * * |
5 | 4 0 0 * |
6 | 5 0 0 |
求右上的三角形即可, 三个方向, 左, 下, 左下, 和算法导论里353页的图思路差不多, 意思不一样而已.
一个自以为比较有意思的空间优化是, 把头顺时针转45度看那个三角形.. 不讲了麻烦, 上代码..
404K 344MS G++
1 | #include <stdio.h> |
2 |
3 | int main() |
4 | { |
5 | int n; |
6 | char a[5010]; |
7 | scanf("%d",&n); |
8 | while(getchar()!='\n'); |
9 | scanf("%s",a); |
10 |
11 | int c[10010]; |
12 | for(int i=2;i<=2*n;i++) { |
13 | c[i]=0; |
14 | } |
15 |
16 | for(int x=1;x<=n-1;x++) |
17 | for(int i=1;i<=n-x;i++) { |
18 | int j=i+x; |
19 | char ai=a[i-1],aj=a[j-1]; |
20 | if(ai==aj) |
21 | continue; |
22 | c[i+j]=c[i+j-1]<c[i+j+1]?c[i+j-1]:c[i+j+1]; |
23 | c[i+j]++; |
24 | } |
25 | printf("%d\n",c[1+n]); |
26 |
27 | return 0; |
28 | } |
