最长回文子序列

问题描述：给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。字符串长度<=5000
示例
输入："abccsb"
返回值：4
说明：子序列bccb回文序列为bccb，因此最长的回文子序列长度为4

方法一

思路分析

     最长回文子序列表示子序列在给定的序列中位置可以是不连续的。使用递归的办法，采用自上而下的办法，要求的string[0,n-1]中开始元素到末尾元素中间的最长回文子序列，有如下递归方程：
  • 设置$lps(string ,i,j)$表示字符串string中第i个位置到第j个位置中的最长回文子序列
  • 设置$lps(string ,i,j)=1，i=j$，同时这也是递归结束的条件
  • 如果首尾元素相同，那么$lps(string ,i,j)=lps(string ,i+1,j-1)+2$
  • 如果首尾元素不同，那么$lps(string ,i,j)=max\{ lps(string ,i+1,j)，lps(string ,i,j-1)\}$

图解

输入："abccsb"，递归过程如下图：
0 1 2 3 4 5
a b c c s b



C++核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        // write code here
        int n=s.size();
        return lps(s,0,n-1);
    }
    int lps(string str, int i, int j)
   {
	if (i == j)    
		return 1;	//只有一个元素，回文长度为1
	if (i > j) return 0;   //因为只计算序列str[i....j]
 
	//如果首尾相同
	if (str[i] == str[j])
		return lps(str, i + 1, j - 1) + 2;
	//如果首尾不同
	return max(lps(str, i, j - 1), lps(str, i + 1, j));
    }

};

复杂度分析

  • 时间复杂度：有许多相同的子问题会被重复计算，这是递归的一个问题，递归的时间复杂度为递归的次数*每次递归的操作次数，递归次数为$n^2$，因此时间复杂度为$O(n^2)$，该方***超时
  • 空间复杂度：递归的空间复杂度为递归的深度*每次递归创建的变量，递归深度为$n$，每次递归的空间复杂度为$O(1)$，因此空间复杂度为$O(n)$

方法二

思路分析

     在使用递归的方法时由于采用自上而下的办法，因此有些子问题被重复计算，为了避免这种问题，我们还可以采用自下而上的办法，即采用动态规划的办法，即借助一个二维数组dp[i][j]存储已经计算过的子问题，即第i个位置到第j个位置最长回文子序列的长度。使用动态规划的转移方程为：
  • 所有连续的长度为i+1的子串，$str[j..j+i]$
  • 如果$dp[i][i]=1 i=j$
  • 如果首尾元素相同那么$dp[j][j+i]=dp[j+1][j+i-1]+2$
  • 如果首尾元素不同那么$dp[j][j+i]=max\{dp[j+1][j+i],dp[j][j+i-1]\}$
  • 最后输出$dp[0][n-1]$即为给定字符串的最长回文子串

C++核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        // write code here
        int n=s.size();
        return lpsDp(s,n);
    }
    int lpsDp(string str, int n)
    {
	int  tmp;
    vector<vector<int>> dp(n,vector<int>(n,0));
	for (int i = 0; i < n; ++i) 	
        dp[i][i] = 1;
	for (int i = 1; i < n; ++i)
	{
		tmp = 0;
		//考虑所有连续的长度为i+1的子串，str[j....j+i]
		for (int j = 0; j + i < n; j++)
		{
			if (str[j] == str[j + i])//如果首尾相同
				tmp = dp[j + 1][j + i - 1] + 2;
			else //如果首尾不同
				tmp = max(dp[j + 1][j + i], dp[j][j + i - 1]);
			dp[j][j + i] = tmp;
		}
	}
	return dp[0][n - 1]; //返回字符串str[0...n-1]的最长回文子序列长度
}
};

复杂度分析

  • 时间复杂度：内外层循环次数为$1+2+3+...+n=n*(n+1)/2$，因此时间复杂度为$O(n^2)$
  • 空间复杂度：借助于一个二维数组存储当前位置的最长回文子序列长度，空间复杂度为$O(n^2)$


方法三

思路分析

      为进一步减小空间的使用，在方法二中可以发现求解$dp[i][j]$数组只与相邻状态有关，因此可以设置一个一维的数组。

python核心代码 

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string 一个字符串由小写字母构成，长度小于5000
# @return int
#
class Solution:
    def longestPalindromeSubSeq(self , s ):
        # write code here
        dp = [1] * len(s)
        for i in range(len(s)-1, -1, -1):
            pre = 0      # dp[i+1][j-1]
            for j in range(i+1, len(s)):
                temp = dp[j]
                if s[i] == s[j]:
                    dp[j] = pre + 2
                else:
                    dp[j] = max(dp[j], dp[j-1])
                pre = temp
        return dp[-1]

复杂度分析

  • 时间复杂度：内外层循环次数为$1+2+3...+n=n*(n+1)/2$，因此时间复杂度为$O(n^2)$
  • 空间复杂度：借助于一个一维数组，空间复杂度为$O(1)$