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

解题思路：

• 建立模型为最长公共子序列。则只要求出s和sr（倒序）的最长公共子序列即可。
• 一般情况：$dp[i][j]=max(dp[i-1][j-1]+(int)(s[i]==sr[j]),max(dp[i-1][j],dp[i][j-1]))dp[i][j]\; =\; max(dp[i-1][j-1]+(int)(s[i]==sr[j]),max(dp[i-1][j],\; dp[i][j-1]))$。
• 处理边界：$dp[0][0]=s[0]==sr[0]dp[0][0]\; =\; s[0]\; ==\; sr[0]$
• 第一行最大值之可能是1： $dp[i][0]=max(dp[i-1][0],(int)(s[i]==sr[0]));dp[i][0]\; =\; max(dp[i-1][0],(int)(s[i]\; ==\; sr[0]));$
• 同理第一列：$dp[0][j]=max(dp[0][j-1],(int)(s[0]==sr[j]))dp[0][j]\; =\; max(dp[0][j-1],\; (int)(s[0]\; ==\; sr[j]))$

#include<bits/stdc++.h>
using namespace std;
int solve(string &s, string &sr, int i, int j, vector<vector<int>> &dp){//递归
    if(dp[i][j] != -1) return dp[i][j];
    if(i == 0 && j == 0) dp[i][j] = s[i] == sr[j];
    else if(i == 0){
        dp[i][j] = max(solve(s,sr,i,j-1,dp), (int)(s[i] == sr[j]));
    }
    else if(j == 0){
        dp[i][j] = max(solve(s,sr,i-1,j,dp), (int)(s[i] == sr[j]));
    }
    else{
        dp[i][j] = max(solve(s,sr,i-1,j-1,dp)+(s[i]==sr[j]),max(solve(s,sr,i,j-1,dp), solve(s,sr,i-1,j,dp)));
    }
    return dp[i][j];
}
int solve2(string &s, string &sr, vector<vector<int>> &dp){//递推
    dp[0][0] = s[0] == sr[0];
    for(int i = 1; i < s.size(); ++i){
        dp[i][0] = max(dp[i-1][0],(int)(s[i] == sr[0]));
    }
    for(int j = 1; j < sr.size(); ++j){
        dp[0][j] = max(dp[0][j-1], (int)(s[0] == sr[j]));
    }
    for(int i = 1; i < s.size();++i){
        for(int j = 1; j < sr.size(); ++j){
            dp[i][j] = max(dp[i-1][j-1]+(int)(s[i]==sr[j]),max(dp[i-1][j], dp[i][j-1]));
        }
    }
    return dp[s.size()-1][sr.size()-1];

}
int solve3(string &s, string &sr){//空间优化递推
    vector<int> dp(s.size()+1);
    vector<int> res(s.size()+1);
    for(int i = 1; i <= s.size(); ++i){
        for(int j = 1; j <= sr.size(); ++j){
            dp[j] = max(res[j-1] + (s[i-1] == sr[j-1]?1:0), max(res[j],dp[j-1]));
        }
        for(int j = 1; j <= sr.size();++j){
            res[j] = dp[j];
        }
    }
    return dp[s.size()];
}                                                            
int main(){
    string s, sr;
    cin>>s;
    int n = s.size();
    sr = s;
    reverse(sr.begin(),sr.end());
    vector<vector<int>>dp(n, vector<int>(n, -1));
    // cout<<solve(s,sr, n-1,n-1, dp)<<endl;
    // cout<<solve2(s,sr, dp)<<endl;
    cout<<solve3(s,sr)<<endl;
    return 0;
}