C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2021-07-05

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

/*
    int longestPalindromeSubSeq(string s) {
        // write code here
        int len=s.size();
        vector<vector<int>> dp(len, vector<int>(len));
        for(int i=len-1; i>=0; --i){
            for(int j=i; j<len; ++j)
                if(i==j)
                    dp[i][j]=1;
                else 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];
    }
*/

C++ 解法, 执行用时: 5ms, 内存消耗: 396KB, 提交时间: 2022-06-12

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

        dp[n - 1] = 1;
        int ld = 0;

        for (int i = n - 2; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                int temp = dp[j];
                if (i == j)
                    dp[i] = 1;
                else if (s[i] == s[j])
                    dp[j] = ld + 2;
                else
                    dp[j] = max(dp[j-1], dp[j]);
                ld = temp;
            }
        }
        return dp[n - 1];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 400KB, 提交时间: 2022-07-12

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        // write code here
        // 反转字符串，借助最长公共子序列方法求解
        int n = s.size();
        if (n == 1)
            return 1;
        string s1 =  s;
        reverse(s1.begin(), s1.end());
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int prev = dp[0];
            for (int j = 1; j <= n; j++) {
                int curr = 0;
                if (s[i - 1] == s1[j - 1]) {
                    curr = prev + 1;
                }
                else {
                    curr = max(dp[j - 1], dp[j]);
                }
                prev = dp[j];
                dp[j] = curr;
            }
        }
        return dp[n];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 404KB, 提交时间: 2022-07-30

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        int n = s.size();
        vector<int> dp(n);
        dp[n-1] = 1;
        for(int i=n-2;i>=0;i--)
        {
            int lastold = 0;
            for(int j=i;j<n;j++)
            {
                if(j==i)dp[j]=1;
                else if(j==i+1)
                {
                    lastold = dp[j];//下一行的dp[j]
                    dp[j]= (s[j]==s[i]?2:1);
                }
                else{
                    int temp = dp[j];
                    if(s[j]==s[i])
                    {
                        dp[j] = lastold+2;
                    }
                    else{
                        dp[j] = max(dp[j-1],dp[j]);
                    }
                    lastold = temp;
                }
                //cout<<dp[j]<<" ";
            }
            //cout<<endl;
        }
        return dp[n-1];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 420KB, 提交时间: 2022-07-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        // write code here
       // 序列s[i]-->s[j]的最长回文子序列的长度
        int n=s.size();
        vector<int> dp(n,1);
        for(int i=n-1;i>=0;--i){
            int pre=0;
            for(int j=i+1;j<n;++j){
                int cur=dp[j];
                if(s[i]==s[j]) dp[j]=pre+2;
                else dp[j]=max(dp[j],dp[j-1]);//dp[j-1]已经更新过了
                pre=cur;//还是之前i-1的
            }
        }
        return dp[n-1];
    }
};