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

相当于求该字串与其翻转后的字串的最长公共子序列

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

int maxSeqLen(const string& s1, const string& s2){    //求两字符串的最大子序列长度
    vector<vector<int>> dpm(2, vector<int>(s2.size(), 0));
    int res = 0;
    for(int i = 0; i < s1.size(); ++i){
        for(int j = 0; j < s2.size(); ++j){
            if(i == 0 && j == 0){
                if(s1[i] == s2[j])
                    dpm[i][j] = 1;
                else dpm[i][j] = 0;
            }
            else if(i == 0){
                if(dpm[i][j-1] || s1[i] == s2[j])
                    dpm[i][j] = 1;
                else dpm[i][j] = 0;
            }
            else if(j == 0){
                if(dpm[(i-1)%2][j] || s1[i] == s2[j])
                    dpm[i%2][j] = 1;
                else dpm[i%2][j] = 0;
            }
            else{
                if(s1[i] == s2[j])
                    dpm[i%2][j] = dpm[(i-1)%2][j-1]+1;
                else dpm[i%2][j] = max(dpm[(i-1)%2][j], dpm[i%2][j-1]);
            }
        }
    }
    return dpm[(s1.size()-1)%2][s2.size()-1];
}

int main(){
    string str;
    cin >> str;
    string rstr = str;
    reverse(rstr.begin(), rstr.end());
    cout << maxSeqLen(str, rstr);
    
    return 0;
}