HDU 1513 Palindrome

題意：求將這個字符串添加成回文串的最少個數

思路：起初按照最土的方法，內存超了，然後就改成了滾動數組，又看了別人的方法，想到這個可以先求出最長的回文子序列，這個有做過，與它的逆序求最長公共子序列，然後再求

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 5005;

int dp[2][MAXN];
int n;
char str[MAXN],tmp[MAXN];

int main(){
	while (scanf("%d",&n) != EOF){
		scanf("%s",str);
		memset(dp,0,sizeof(dp));
		for (int i = n-1; i >= 0; i--)
			for (int j = i+1; j < n; j++)
				if (str[i] == str[j])
					dp[i%2][j] = dp[(i+1)%2][j-1];
				else dp[i%2][j] = min(dp[(i+1)%2][j],dp[i%2][j-1])+1;

		printf("%d\n",dp[0][n-1]);
	}
	return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 5005;

int dp[2][MAXN],n;
char str1[MAXN],str2[MAXN];

int main(){
	while (scanf("%d",&n) != EOF){
		memset(str1,0,sizeof(str1));
		memset(str1,0,sizeof(str2));
		scanf("%s",str1);
		for (int i = 0; i < n; i++)
			str2[i] = str1[n-i-1];
		memset(dp,0,sizeof(dp));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (str1[i-1] == str2[j-1])
					dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
				else dp[i%2][j] = max(dp[i%2][j-1],dp[(i-1)%2][j]);
		printf("%d\n",n-dp[n%2][n]);
	}
	return 0;
}