题目描述
给定一个字符串S ，找到其中最长的回文子序列，并返回该序列的长度。
输入描述
输入为一个只包含小写英文字母的字符串S，最大长度不超过4000。
输出描述
输出最长回文子序列的长度。
测试用例
输入
abcb
输出
3
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 4005
ll dp[MAXN][MAXN];
string s;
int main(){
cin >> s;
ll n = s.size();
for (ll i = 1; i <= n; i++)
dp[i][i] = 1;
for (ll i = 1; i <= n; i++){
for (ll j = 1; j + i <= n;++j){
if(s[j-1] == s[j+i-1])
dp[j][j+i] = dp[j+1][j+i-1] + 2;
else
dp[j][j+i] = max(dp[j+1][j+i], dp[j][j+i-1]);
}
}
cout << dp[1][n];
return 0;
}