怎么把非回文字符串添加最少的字符成为回文字符串

我觉得应该是

从原始的字符串的第j个位置

提取出i个字符形成的子串

需要添加f[i][j]个字符可以形成回文

按照这个思路

初始化

for(i

=

0

i

<

n

i++)

{

f[0][i]

=

0

f[1][i]

=

0

}

对于任意位置

提取出0或者1个字符

自然可以认为是回文

不需要添加字符

即添加0个字符

事实上

这个循环可以去掉

因为上面已经有

memset(f,

0,

sizeof(f))

然后对子串大小进行循环

这个是外循环

对每个大小的子串

进行提取位置的循环

这个是内循环

核心转移公式

if(s[j]

==

s[i+j-1])

{

f[i][j]

=

f[i-2][j+1]

}

else

if(f[i-1][j]

<

f[i-1][j+1])

{

f[i][j]

=

f[i-1][j]

+

1

}

else

f[i][j]

=

f[i-1][j+1]

+

1

对于从第j位提取长度为i的子串

如果这个子串的第一位s[j]和最后一位

s[i+j-1]相同

那么其需要添加的数量和去掉这两个字符后需添加数量相同

即f[i-2][j+1]

如果不同的话

那么由于i-1长度下最优方案已计算，这样要么在开头加结尾字符

要么在结尾加开头字符

转化为i-1长度的最佳方案递推

比较去头或者去尾的情况

选其较小者+1

即为当前最佳方案

最难理解的在于不等于这一步

多想一下f[i][j]的含义

如果还想不明白

再追问

我们继续讨论

PS：程序问题

不知道题目要求的最长可能输入是多少

但是从代码上看

可能是最长不超过1000个字符

这样对s[i+j-1]访问实际上是可能越界的

虽然不影响结果

因为相邻的是f

其开始部分一直为0

但并不是合格程序应有的

应该定义的空间为

s[2*max_len+1]

l[max_len+1][max_len+1]

program cs

const n=10000

var

s:array[1..n] of char

i,j:integer

c:string

begin

readln(c)

if (length(c) mod 2)<>0 then

begin

delete(c,(length(c) div 2)+1,1)

end

//删去奇数个字符中间字符。

i:=0j:=1

while j<=length(c) do

begin

if i=0 then

begin

inc(i)

s[i]:=c[j]

inc(j)

end//栈空，则直接压栈。

else

begin

if s[i]=c[j] then

begin

dec(i)

inc(j)

end//栈顶元素与当前字符相同，就出栈。

else

begin

inc(i)

s[i]:=c[j]

inc(j)

end//不同，就进栈。

end

end

if i=0 then writeln('True')

else writeln('False')//如果栈是空的，证明是回文。

end.

思路是对于奇数个字符，删去中间字符。

其余字符扫一个处理一个，s[]是栈，i是它的指针。

j是c的指针。