测试如下数据都可以

10
2514785444
输出6

5
Ab3bd
输出2


#include <iostream>
using namespace std;

#define MAX 5001 
int AA[MAX][MAX];
char SA[MAX];
char SB[MAX];
int len;


int foo(int raw,int col){
	if(raw >= len || col >= len){
		return 0;
	}
	if(AA[raw][col] != -1)
		return AA[raw][col];
	int tmp;
	if(SA[col] == SB[raw]){
		tmp = foo(raw + 1,col + 1) + 1;
	}else{
		int left = foo(raw , col + 1);	
		int down = foo(raw + 1, col);
		tmp = (left > down)?left : down;	
	}
	AA[raw][col] = tmp;
	return tmp;
}

int main(){
	memset(AA,-1,sizeof(AA));
	cin >> len;
	getchar();
	gets(SA);
	for(int i = 0; i < len ; ++i){
		SB[i] = SA[len - i -1];
	}
	cout << len - foo(0,0) << endl;
}