通过删除字符从现有字符串创建回文

Question

如何通过删除零个或多个字母来确定从单词中获得的最长回文的长度.

例如:amanQQQapl12345anacaZZZnalpaXXXna67890ma
最长的回文将是21位数.

Answer 1

这可以通过动态编程来解决.将d [i,j]定义为原始字符串中最长回文的长度.

如果s [i] = s [j],则d [i,j] = max(d [i + 1,j-1] + 2,d [i,j-1],d [i + 1,j] ).

否则d [i,j] = max(d [i,j-1],d [i + 1,j]).