LeetCode 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: “bbbab”
Output: 4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input: “cbbd”
Output: 2
One possible longest palindromic subsequence is “bb”.

解析：
最长回文子序列，此题目要求是最长子序列，而不是子串，子序列可以不连续。考虑动态规划算法。
采用一个二维的DP数组，其中dp[i][j]表示[i,j]区间内的字符串的最长回文子序列，那么对于递推公式我们分析一下，如果s[i]==s[j]，那么i和j就可以增加2个回文串的长度，我们知道中间dp[i + 1][j – 1]的值，那么其加上2就是dp[i][j]的值。如果s[i] != s[j]，那么我们可以去掉i或j其中的一个字符，然后比较两种情况下所剩的字符串谁dp值大，就赋给dp[i][j]。递推公式如下：

代码如下：

class Solution 
{
	public:
	int longestPalindromeSubseq(string s) 
	{
		int len = s.size();
		vector<vector> dp(len, vector(len));
		for (int i = len -1; i >=0; i--) 
		{
			dp[i][i] = 1;
			for (int j=i+1; j < len; j++) 
			{
				if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
			}
		}
		return dp[0][len-1];
	}
}
;

此种解法时间复杂度为\(O(n^2)\)，时间复杂度为\(O(n^2)\)。

解法2: 观察解法1的递推公式可以发现dp[i][j]实际只与dp[i+1][j-1],dp[i+1][j], dp[i][j-1]。可以考虑降低计算空间复杂度。 dp[i]表示从i起始的最长回文序列。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        int result = 0;
        vector<int> dp(n,1);
        for(int i=1; i < n; i++)
        {
            int len = 0;
            for(int j=i-1; j >=0; j--)
            {
                int temp = dp[j];
                if(s[i] == s[j])
                    dp[j] = len + 2;
                len = max(len, temp);
            }
        }
        for(auto i: dp)
            result = max(result, i);
        return result;
        
    }
};

两种解法的时间和空间对比如下：