题意是说，给定一个字符串，问至少还需要插入多少个字符才能使得该字符串成为回文字符串。
这道题一开始做的时候用了一个简单的动态规划，开了一个5000*5000的数组，用递归形式实现，代码如下：
其中d[i][j]表示i到j所需要插入的字符数。然而数组开得太大直接报MLE。因此想到用滚动数组来解决。
MLE代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
//内存超限 MLE
const short maxn=+;
int d[maxn][maxn];//d表示i到j形成回文串所需加入的字符数
string s;
int dp(int i,int j){
if(d[i][j]>=)return d[i][j];
if(i<j){
if(s[i]==s[j]){
d[i][j]=dp(i+,j-);
return d[i][j];
}
else{
d[i][j]=min(dp(i+,j),dp(i,j-))+;
return d[i][j];
}
}
else if(i==j){
d[i][j]=;
return ;
}
}
int main(void){
int n;
scanf("%d",&n);
cin>>s;
memset(d,-,sizeof(d));
int ans=dp(,n-);
cout<<ans<<endl;
return ;
}
使用滚动数组的动态规划和上述略有不同。基本算法如下：
设输入为X，则记X的逆序列为Y，其中X的字符个数为n,
那么ans=n-(X和Y的最大公共子序列长度）。这样就将该问题转化为了求最长公共子序列的问题。
则此时令d[i][j]表示为X序列和Y序列在前I项和前j项的最大公共序列的长度。
具体状态转移方程见代码或最长公共子序列题的动态转移方程。
但此时的d[i][j]仍然是5000*5000的数组，而由状态转移方程可以发现，在递推过程中其实只涉及两层数组内容，因此可以只保留两层数组从而将数组减小为2*5000的滚动数组。
AC代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
//线性动态规划，滚动数组
const int maxn=+;
int d[][maxn];
int main(void){
int n;
while(cin>>n){
string s1,s2;
cin>>s1;
s2=s1;
reverse(s1.begin(),s1.end());
memset(d,,sizeof(d));
int n=s1.length();
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(s1[i-]==s2[j-]){
d[i%][j]=d[(i-)%][j-]+;
}
else{
d[i%][j]=max(d[(i-)%][j],d[i%][(j-)]);
}
}
}
cout<<n-d[n%][n]<<endl;
}
return ;
}