#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; const int maxn=5005; short int dp[2][maxn]; int n; string str1; string str2; int lenth1,lenth2; void lcs() { memset(dp,0,sizeof(dp)); lenth1=str1.length();//length返回string中字符的个数 lenth2=str2.length(); int flag=0; for(int i=0; i<=lenth1; i++) { flag=1-flag;//i-1==1-flag,i==flag for(int j=0; j<=lenth2; j++) { if(i==0||j==0) dp[flag][j]=0; else if(str1[i-1]==str2[j-1]) dp[flag][j]=dp[1-flag][j-1]+1; else dp[flag][j]=max(dp[1-flag][j],dp[flag][j-1]); } } } void swapp() { str2=str1; for(int i=0; i<n; i++) str2[i]=str1[n-1-i]; } int main() { cin>>n; cin>>str1; swapp(); lcs(); printf("%d\n",n-max(dp[0][lenth2],dp[1][lenth2])); return 0; }

这是一段C++代码，实现了求解最长回文子序列问题。具体来说，该程序输入一个正整数n和一个字符串str1，然后将字符串str1反转得到字符串str2。接着，使用动态规划算法求解字符串str1和str2的最长公共子序列，最后输出n减去最长公共子序列的长度，即为最长回文子序列的长度。

具体实现过程中，定义了一个二维数组dp，其中dp[i][j]表示字符串str1的前i个字符和字符串str2的前j个字符的最长公共子序列长度。然后使用循环遍历字符串str1和str2的所有前缀字符，根据字符是否相等，更新dp数组中的元素。最后输出n减去dp[0][lenth2]和dp[1][lenth2]中的最大值，即为最长回文子序列的长度。

需要注意的是，该程序采用了滚动数组的技巧，用flag变量来表示当前使用的是dp数组的哪一行。这样可以减小空间复杂度。