使用最少的插入将字符串转换为回文字符串

Question

为了找到将给定字符串转换为回文所需的最小插入次数,我找到了字符串(lcs_string)及其反向的最长公共子序列.因此,要进行的插入次数是length(s) - length(lcs_string)

知道要插入的数量,应该采用什么方法来找到等效的回文串？

例如 :

1)azbzczdzez

所需插入次数:5 Palindrome字符串:azbzcezdzeczbza

虽然同一根弦可能存在多个回文弦但我只想找到一个回文？

Answer 1

Let S[i, j]表示S从索引开始i并以索引j(包括两者)结束的字符串的子字符串,并且c[i, j]是最佳解决方案S[i, j].

显然,c[i, j] = 0 if i >= j.

一般来说,我们有重复: