学步园

假设有指针i,j指向字符串的首尾，即初值为0,n-1。

如果字符相等，则总插入次数等于字符串(i+1,j-1)的总插入次数。

如果字符不相等，则有在i处插入一个和j处相等的字符和在j处插入和i处相等的字符两种选择，选择的依据是字符串(i,j-1)总插入次数和字符串(i+1,j)哪个小。

由此子问题和递推关系都有了。

然后是边界条件。设字符串(i,j)总插入次数是res[i][j]。

注意到i<j，因此只需要计算一半的矩阵。边界有i=j时，res[i][j]=0。

计算每个子问题，最后矩阵右上角res[0][n-1]即为所求。

#include<iostream>
#include<fstream>
using namespace std;
int n;
char str[5001];
short res[5002][5002];
int main(){
	streambuf *backup;   
    ifstream fin;   
    fin.open("data.in");   
    backup = cin.rdbuf();   // back up cin's streambuf   
    cin.rdbuf(fin.rdbuf()); // assign file's streambuf to cin
	
	cin>>n;	
	cin>>str;	
	memset(res,0,sizeof(res));
	for(int i=0;i<n;i++){
		res[i][i]=0;
	}
	for(int i=0;i<n-1;i++){
		res[i][i+1]=(str[i]==str[i+1]?0:1);
	}	
	int x;
	for(int i=2;i<n;i++){
		x=0;
		for(int y=i;y<n;y++){
			if(str[x]==str[y]){
				res[x][y]=res[x+1][y-1];
			}else{
				res[x][y]=min(res[x+1][y],res[x][y-1])+1;
			}
			x++;
		}
	}
	cout<<res[0][n-1]<<endl;
	return 0;
}

但是这样做时间空间消耗都很大。我想到不一定每个子问题都用得到，因为当两个字符相等的时候只用了res[x+1][y-1]，那么res[x+1][y]和res[x][y-1]就不用计算了，那么相关的一连串子问题都不用计算了。所以我又自顶向下用了递归，但是还是把结果保存，仍然是dp。

#include<iostream>
#include<fstream>
using namespace std;
int n;
char str[5001];
short res[5002][5002];
short f(int x,int y){
	if(res[x][y]==-1){
		if(str[x]==str[y]){
				res[x][y]=f(x+1,y-1);
		}else{
				res[x][y]=min(f(x+1,y),f(x,y-1))+1;
		}
	}
	return res[x][y];
}
int main(){
	streambuf *backup;   
    ifstream fin;   
    fin.open("data.in");   
    backup = cin.rdbuf();   // back up cin's streambuf   
    cin.rdbuf(fin.rdbuf()); // assign file's streambuf to cin
	
	cin>>n;	
	cin>>str;	
	memset(res,-1,sizeof(res));
	for(int i=0;i<n;i++){
		res[i][i]=0;
	}
	for(int i=0;i<n-1;i++){
		res[i][i+1]=(str[i]==str[i+1]?0:1);
	}	
	cout<<f(0,n-1)<<endl;
	return 0;
}

poj提交上去，效率提升并不大，不过我觉得总体来说应该还是有一定提升效率的作用。

进一步研究空间，可以发现矩阵只用了一半，另一半完全可以舍弃，另外，每回合计算只涉及到与对角线平行的三条线（画矩阵就看出来了），因此res有三行就够了。把上面代码用到的index映射到这三行，三行一直roll着用就可以了。

#include<iostream>
#include<fstream>
using namespace std;
int n;
char str[5001];
short res[3][5002];
int main(){
	//streambuf *backup;   
 //   ifstream fin;   
 //   fin.open("data.in");   
 //   backup = cin.rdbuf();   // back up cin's streambuf   
 //   cin.rdbuf(fin.rdbuf()); // assign file's streambuf to cin
	//
	cin>>n;	
	cin>>str;	
	memset(res,0,sizeof(res));		
	int s,m,e,y;
	s=0;m=1;e=2;	
	for(int i=1;i<n;i++){
		y=i;
		for(int x=0;x<n-i;x++){
			if(str[x]==str[y]){
				res[e][x]=res[s][x+1];
			}else{
				res[e][x]=min(res[m][x],res[m][x+1])+1;
			}
			y++;
		}
		if(i!=n-1){
			s=(s+1)%3;
			m=(m+1)%3;
			e=(e+1)%3;
		}
	}	
	
	cout<<res[e][0]<<endl;
	return 0;
}