题解 | #最长回文子序列#

NC154 最长回文子序列

题意

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。字符串长度 $\le5000$

1. 暴力做法(不合要求， tle)

递归计算区间[i, j]的最长回文子序列，设最长回文子序列为f(i, j), 分为三种情况：

如果s[i] == s[j], 那么最长子序列可能是2+f(i-1, j-1)
否则，i和j不能同时取到，最长子序列可能是f(i-1, j)和f(i, j-1) 的最大值。

分别递归计算上面三种情况的较大值即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    string s;
    int longestPalindromeSubSeq(string s2) {
        int n = s2.size();
        s = s2;
        return f(0, n-1);
    }

    int f(int i, int j) {
        if (i == j) return 1; // 只有1个元素，答案是1
        if (i > j) return 0; // 如果区间不合法，没有方案

        int res = -1;
        if (s[i] == s[j]) res = max(res, f(i+1, j-1)+2); // 头尾是相同元素，多一种情况
        res = max(res, f(i+1, j));
        res = max(res, f(i, j-1));
        return res;
    }
};

时间复杂度: $O(2^n)$ , 每个字符都枚举了选择和不选择两种情况
空间复杂度: $O(2^n)$ , 每层递归都占用了 $O(1)$ 的空间。

2. 区间DP

事实上方法1如果加上了记忆化搜索，就得到了一种区间DP的思路，设dp[i][j]表示区间[i, j]的最长回文子序列，则有以下关系：

如果s[i] == s[j], dp[i][j] = max(dp[i][j], dp[i-1][j-1]+2)
否则，i和j不能同时取到，dp[i][j] = max(dp[i+1][j] ,dp[i][j-1]

最后dp[0][n-1]就是答案。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    static const int N = 5010; // 题目注释中说s的最大长度是5000，所以这里开5000*5000的数组
    int dp[N][N];
    int longestPalindromeSubSeq(string s) {
        int n = s.size();
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) dp[i][i] = 1;

        // 重点注意，i跟i+1有关，j跟j-1有关，所以i要倒过来算
        // 如果i是正向算的，那么dp[i+1]还没算出来，就会wa
        for (int i = n-1; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                if (s[i] == s[j]) 
                    dp[i][j] = max(dp[i+1][j-1]+2, dp[i][j]);
            }
        }

        return dp[0][n-1];
    }
};

时间复杂度: $O(n^2)$ , 两重循环。
空间复杂度: $O(n^2)$ , 开了二维数组。

3. 转化为lcs模型，dp

我们发现回文串有一个重要的特点，正序和逆序是一样的，那么，如果我们把s倒过来得到串t，那么s的最长回文子序列不就是s和t的最长公共子序列吗？

我们用一个图来描述下：

图片说明

那么黄色部分正着看和倒着看是一样的，因此可以使用lcs的模型来计算，接下来套用lcs问题的模板就可以了。

lcs问题的解法简单描述如下，设dp[i][j]表示s串和t串的前i个字符和前j的字符的子串的最长公共子序列。那么有如下的转移关系：

如果s[i] == t[j], 则dp[i][j] = dp[i-1][j-1]+1
否则s[i]和t[j]一定有一个不在答案中，则dp[i][j] = max(dp[i-1][j], dp[i][j-1]

转移过程如下图所示：

图片说明
最后，本题中s和t的长度一样，则 $dp[n][n]$ 即为答案。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */

    static const int N = 5010; 
    int dp[N][N];

    int longestPalindromeSubSeq(string s) {
        int n = s.size();
        string t = s;
        // 求s的逆序串t
        reverse(t.begin(), t.end());

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                if (s[i-1] == t[j-1]) // dp序列从1开始，而s和t下标从0开始，故减1修正
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
            }
        }

        return dp[n][n];
    }
};

时间复杂度: $O(n^2)$ , 两重循环。
空间复杂度: $O(n^2)$ , 开了二维数组。