(1)思路：最长公共子序列：ans=L-LCS(s,^s)
(2)DP 状态：dp[i][j]为i to j，需要加入的字符。初始：dp[i][i]=0
分2种情况：s[i]==s[j]则dp[i][j]=dp[i+1][j-1]
s[i]!=s[j] =Min(dp[i+1][j],dp[i][j-1])+1
dp[i][j]=cal(i+1,j-1);
return dp[i][j];
}
/**//*dp[i][j]=MIN(cal(i+1,j-1)+2,cal(i+1,j)+1);
dp[i][j]=MIN(dp[i][j],cal(i,j-1)+1);*/
dp[i][j]=MIN(cal(i+1,j)+1,cal(i,j-1)+1);
return dp[i][j];
}
int main()
{
int i,j,k,mid;
scanf("%d",&N);
//for(i=0;i<N;i++)
scanf("%s",s);
len=strlen(s);
//printf("%d\n",len);
mid=len/2;
memset(dp,-1,sizeof(dp));//unsigned to the utmost
dp[mid][mid]=0;
printf("%d\n",cal(0,len-1));
return 0;
}
(3)节省空间，用dp[2][5002]的数组存放。因为i-1用过后，就不再用了
滚动数组最直接的想法就是利用原来第i-1行的空间来计算接下来要算的i+1行
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define MIN(a,b) (a)<(b)?(a):(b)
char s[5002];
int dp[2][5002];
int main()
{
int i,j,k,l,N;
scanf("%d",&N);
scanf("%s",s);
for(i=N-1;i>=0;i--)
for(j=i+1;j<N;++j)
if(s[i]==s[j])dp[i&1][j]=dp[(i+1)&1][j-1];
else dp[i&1][j]=MIN(dp[(i+1)&1][j]+1,dp[i&1][j-1]+1);
printf("%d\n",dp[(i+1)%2][N-1]);
return 0;
}
这样就可以用一个array[2][]的数组，在两行之间交替计算
（4）
特殊情况：计算array[i][j]所用到的第i-1行的元素全部都在j列的左边
array[i-1][j]和array[i-1][j-1]
然后这种情况可以只用一维数组，按照从右到左的顺序计算
array[j] = array[j-1]+array[j]
重复i次
每次从右到左将一行的元素都按照array[j] = array[j-1]+array[j]计算
假设这个一维数组现在存的是i-1行的元素，计算第i行的元素时，直接将它记
录在这个一维数组对应的位置上
因为是从右向左计算，而计算只需要左边的元素，所以新存进去的元素不会影响后面元素的值
#include <stdio.h>
#include <string.h>
int main()
{
char a[5002];
int f[5002];
int i,j,n,t,tp;
scanf("%d%s",&n,a+1);
memset(f,0,sizeof(f));
for(i=1;i<=n;i++){
tp=0; //f[i-1,j-1]复位，一开始忘记了，老是wa，郁闷
for(j=n;j>=1;j--){
if(a[i]==a[j]){
t=f[j];
f[j]=tp+1; //f[i,j]=f[i-1,j-1]+1
tp=t;
}
else{
tp=f[j];
if(f[j]<f[j+1]) f[j]=f[j+1]; //f[i-1,j]<f[i,j-1]
}
}
}
printf("%d\n",n-f[1]);
return 0;
}