#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false), cin.tie(0); typedef long long LL; const int N=1010; int n; string s; int dp[N][N]; //dp[i, j]表示索引[i, j]的最长回文子序列长度 int main() { IOS cin>>s; n=s.size(); 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; else dp[i][j]=max(dp[i+1][j], dp[i][j-1]); } } cout<<dp[0][n-1]; return 0; }
经典二维dp,定义状态dp[i, j]表示字符串中[i, j]的最长回文子序列,考虑s[i]和s[j]的关系,相同那就是转移
不相同那就三种情况,但是可以被max(dp[i+1][j], dp[i][j-1])完全包含
最后输出dp[0, n-1]