C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-06-16

#include <iostream>
#include <vector>

using namespace std;

int main(){
    
    string str;
    cin>>str;
    
    int strLen=str.length();
    
    vector<int> dpPre(strLen,0);
    vector<int> dpNext(strLen,0);
    
    for(int i=0;i<strLen;i++){
        for(int j=i;j>=0;j--){
            if(i==j){
                dpNext[j]=1;
            }else if(i==j+1){
                if(str[i]==str[j]){
                    dpNext[j]=2;
                }else{
                    dpNext[j]=1;
                }
            }else{
                if(str[i]==str[j]){
                    dpNext[j]=max(max(dpNext[j+1],dpPre[j]),dpPre[j+1]+2);
                }else{
                    dpNext[j]=max(dpPre[j],dpNext[j+1]);
                }
            }
            
        }
        dpPre=dpNext;
    }
    cout<<dpNext[0]<<endl;
    return 0;
}

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

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int MPS(string& s);
int main() {
    string s;
    getline(cin, s);
    cout << MPS(s) << endl;
    return 0;
}
int MPS(string& s) {
    int n = s.size();
    vector<int> d(n, 0);
    for (int i = 0; i < n; i++)
        d[i] = 1;
    for (int i = n - 2; i >= 0; i--) {
        int p = 0;
        for (int j = i + 1; j < n; j++) {
            int t = d[j];
            if (s[i] == s[j]) d[j] = p + 2;
            else d[j] = max(d[j], d[j - 1]);
            p = t;
        }
    }
    return d[n - 1];
}

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

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int longestPalindromeSubsequence(string &s);
int main(){
    string s;
    getline(cin,s);
    cout<<longestPalindromeSubsequence(s)<<endl;
    return 0;
}
int longestPalindromeSubsequence(string &s){
    int n=s.size();
    vector<int> dp(n,0);
    for(int i=0;i<n;i++)
        dp[i]=1;
   
    for(int i=n-2;i>=0;i--){
         int pre=0;
        for(int j=i+1;j<n;j++){
            int temp=dp[j];
            if(s[i]==s[j]) dp[j]=pre+2;
            else dp[j]=max(dp[j],dp[j-1]);
             pre=temp;
        }
    }
    return dp[n-1];
}

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

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char **argv)
{
    string str1;
    while(cin >> str1){        
        int n = str1.length();
        vector<int> dp(n + 1, 0);
        vector<int> dpLast(n + 1, 0);
        for(size_t j = n; j >= 1; j--){
            for(size_t i = 1; i <= n; i++){
                if(str1[i - 1] == str1[j - 1]){
                    dp[i] = dpLast[i - 1] + 1;
                } else{
                    dp[i] = max(dp[i - 1], dpLast[i]);
                }
                dpLast[i - 1] = dp[i - 1];
            }
            dpLast[n] = dp[n];
        }
        cout << dp[n] << endl;
    }
    
    return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 436KB, 提交时间: 2022-03-05

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
    string x,y;
    cin>>x;
    y=x;
    reverse(x.begin(),x.end());
    vector<int> dp(x.size()+1,0),his(x.size()+1,0);
    for(int i=0;i<x.size();i++)
    {
        for(int j=0;j<y.size();j++)
           if(x[i]==y[j])
             dp[j+1]=his[j]+1;
           else
             dp[j+1]=max(dp[j+1],dp[j]);
        for(int k=0;k<=x.size();k++)
            his[k]=dp[k];
    }
    cout<<dp[x.size()];
}