516.最长回文子序列 (Medium)*

题目描述*

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例*

输入: "bbbab"

输出: 4

输入: "cbbd"

输出: 2

代码*

二维动态规划求解，dp[i][j] 为子串 s[i...j] 中最长回文子序列的长度。如果 str[i] == str[j] 那么将他们加入到 str[i+1...j-1] 间的子串即可。如果不相等，可分别加入 str[i+1...j-1] 间的子串，看哪个子序列更长。我们要求的就是 dp[0][len - 1]。

再考虑初始状态，dp[i][i] = 1, dp[i][j] = 0 (i < j)，也就是从数组的左下遍历最后计算出右上角。遍历顺序为 i:n-1~0, j:1~n-1。

二维 dp 还是比较慢，优化可以压缩为一维 dp。

二维 dp一维 dp

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        if(len == 0) {
            return 0;
        }
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for(int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        for(int i = len - 1; i >= 0; i--) {
            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] = (dp[i + 1][j] >= dp[i][j - 1]) ? dp[i + 1][j] : dp[i][j - 1];
                }
            }
        }
        return dp[0][len - 1];
    }
};

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

最后更新: July 23, 2022