516、最长回文子序列

                                                                                                                                            点击此处返回总目录

【题目】

注意，子序列跟子串是不一样的。子序列是从字符串中取出元素，相对顺序不变，但是可以不挨着。子串肯定是截取一段。

【方法一：记忆化搜索】

假设fun(char[] S , int i , int j) 返回的是串S[i...j]的最长回文子序列。

则如果S[i]==S[j] , 则：fun(S, i , j) = 2+fun(S , i+1 , j-1)

如果不等，则，fun(S , i , j) = max{ fun(S, i+1 , j) ,  fun(S , i , j-1)}

递归写法如下：

很显然，会超时：

因为计算了很多遍重复的。

因此，需要进行改进：将中间结果进行保存。下次计算的时候就不需要重复计算了。这就是记忆化搜索的方法。

代码：

结果：

【方法二：动态规划】

设dp[i][j]为从i到j的字符串，回文子序列的最大长度。

比如："bbbab"

建立dp[][]：

首先长度为1的字符串，最大回文子序列的长度为1。比如"a"。所以：dp[i][i]=1。所以：

然后求长度为2的字符串。如"bb"''ba''等。只需要判断两边字符是否相等即可。相等则为2，不相等则为1。所以：

对于长度k>=3的字符串。需要用dp式子来求。如"bbb"、"bba"等。

代码：

结果：

时间复杂度：o(n^2)

效果不太好。但是按道理递推式要比递归式子好，可能是因为我的递推式子，变量计算太多导致。我看了一下其他人代码，确实快一些，但是不清晰，里面用到了d[i][j] （i<j）这样的值。也就是说没有完全用到前面计算出的结果。

注：

我在看相关的书和博客的时候，有下面一些叫法，感觉都一样：

记忆化搜索 =   记忆递归型的动态规划    =  记忆化递归

动规            =  递推型动态规划

叫法就不纠结了。