516. Longest Palindromic Subsequence

区间型dp O(n²) time O(n²) space
f[i][j]表示s[i:j]最长回文子序列的长度

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

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

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size(), res = 0;
        vector<int> dp(n, 1); // dp[i]表示以s[i]为止的最长回文子序列的长度
        for (int i = n - 1; i >= 0; --i) {
            int len = 0; // len是s[i:j]两边exclusive（即s[i + 1 : j - 1]）之内的最长回文子序列的长度
            for (int j = i + 1; j < n; ++j) {
                int t = dp[j]; // 保存s[i + 1 : j]两边inclusive的最长回文子序列的长度
                if (s[i] == s[j]) {
                    dp[j] = len + 2;
                }
                len = max(len, t);
            }
        }
        for (int num : dp) res = max(res, num);
        return res;
    }
};

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

O(n²) time O(n) space
roll array

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(t.begin(), t.end());
        int n = s.length();
        vector<vector<int>> dp(2, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (t[i - 1] == s[j - 1]) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                } else {
                    dp[i % 2][j] = max(dp[i % 2][j - 1], dp[(i - 1) % 2][j]);
                }
            }
        }
        return dp[n % 2][n];
    }
};

O(n²) time O(n²) space
最长公共子序列的变种
s是正序，t是倒序，求s和t的最长公共子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(t.begin(), t.end());
        int n = s.length();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (t[i - 1] == s[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n][n];
    }
};