学步园

这题有两种方法，一种是用lcs来做，另外就是dp，不过其实现都差不多，内存方面还可以进一步优化，只开一个n的一维数就可以

做这题时出现了一件怪事，点怪看代码

递推式：

            c[i][j] = 0 i >= j;

                     = c[i+1][j-1]    si = sj;

                    = min(c[i][j-1],c[i+1][j])+1     si!= sj;

#include<iostream>
#include<string>
#include<vector>

#define N 5005

using namespace std;

string s;
int d[2][N];

void dp(){
	memset(d,0,sizeof(d));
	for(string::size_type i = s.size()-1;i > 0;i--){
		for(string::size_type j = i+1;j < s.size();j++){
			if(s[i] == s[j])
				d[i%2][j] = d[(i+1)%2][j-1];
			else{
				d[i%2][j] = d[(i+1)%2][j] < d[i%2][j-1]? (d[(i+1)%2][j]+1):(d[i%2][j-1]+1);
			}
		}
		//for(int t = 0;t < s.size();t++)//为什么加上这个后s串都变为空格了呢？本来不打算用i%2的
		//	d[2][t] = d[1][t];
	}
	cout <<d[1][s.size()-1] <<endl;
	//return d[1][s.size()-1];
}

int main()
{
	int n;
	while(cin >>n){
		cin >>s;
		s = " "+s;
		dp();
	}
	return 0;
}