题目大意：
给你一个字符串，问你最少加上几个字符可以得到一个回文串


思路：
给一个字符串添加字符，使其变成回文字符串。这个过程可以看成是：对这个字符串两边同时进行处理，让两边第一个字符一样了，然后删去两边的这个字符，再继续进行。

理论递推关系：
使该字符串前i个和后j个完全相同至少所需添加的字符个数=min{使该字符串前i个和后j-1个完全相同的个数+1 ；使该字符串前i-1个和后j个完全相同的个数+1 ；使该字符串前i-1个和后j-1个完全相同的个数+2/0（第i个和倒数第j个字符不相同/相同）}


递推关系代数化：
设使该字符串前i个和后j个完全相同至少所需添加的字符个数为a[i][j];字符串有n个字符。

if(c[i]!=r[n+1-j])  a[i][j]=min{a[i-1][j],a[i][j-1],a[i-1][j-1]+2};
else  a[i][j]=min{a[i-1][j],a[i][j-1],a[i-1][j-1])};
起始条件（边界条件）：a[i][0]=a[0][i]=i;(0<=i<=n)

还有一个问题就是：递推之后，答案是a[?][?]。
这个就可以理解成是a[?][?]的时候，该字符串就变成了回文串。然后根据表达的意思，应该是min{a[i][j](i+j==n||i+j==n-1)}。(n为字符总个数)

没仔细看，内存太小了！得用滚动数组（不知道是不是这个名字），反正就是两个一维数组滚动着用呗。也没仔细看时间复杂度，这么仔细一想，时间复杂度O(n^2)；

 

#include #include #include #include #define N 5500 #define inf 0x3f3f3f3f using namespace std; char c[N]={0}; int a[2][N]={0}; int n; void input() { cin>>n; for(int i=1;i<=n;i++) { cin>>c[i]; } } void init() { memset(a,0,sizeof(a)); for(int i=0;i<=n;i++) { a[0][i]=i; a[1][i]=0; } } int my_min(int a,int b,int c) { int min=a; if(min>b)min=b; if(min>c)min=c; return min; } int dp() { bool x=1;//第一行一开始已经赋值了 int min=inf; for(int i=1;i<=n;i++) { for(int j=1;j<=n-i;j++) { a[x][0]=i; a[!x][0]=i-1; if(c[j]==c[n-i+1]) { a[x][j]=my_min(a[!x][j]+1,a[x][j-1]+1,a[!x][j-1]); } else { a[x][j]=my_min(a[!x][j]+1,a[x][j-1]+1,a[!x][j-1]+2); } //cout<a[x][j])min=a[x][j]; } } x=!x; //cout<

之后查了题解，别人的一句话，很6啊：寻找串与其逆串的最长公共子序列。因为此子序列必是回文串，剩下的字符就是需要插入的。