POJ1159Palindrome

http://poj.org/problem?id=1159

题意 ： 给定一个字符串，问最少插入多少字符，使该字符串变成回文串

思路 ： 设原字符串序为X，逆序列为Y，则最少需要补充的字母数 = X的len减去X和Y的最长公共子序列的长度，又是一个动态规划问题，这个题的数据范围到5000，倒不是说会超时，但是会超内存，在书上看了一个很好的方法就是滚动数组，感觉挺新鲜的，也挺厉害的，但是滚动数组只节省空间，不省时间

#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
int dp[3][5200];
int main()
{
    string s1,s2 ;
    int n,i,j ;
    while(cin >> n)
    {
        cin>>s1 ;
        s2 = s1 ;
        reverse(s1.begin(),s1.end());
        memset(dp,0,sizeof(dp)) ;
        for(i = 1 ; i <= n ; i++)
        {
            for(j = 1 ; j <= n ; j++)
            {
                dp[i%2][j] = max(dp[(i-1)%2][j],dp[i%2][j-1]) ;
                if(s1[i-1] == s2[j-1])
                {
                    int temp = dp[(i-1)%2][j-1]+1 ;
                    dp[i%2][j] = max(dp[i%2][j],temp);
                }
            }
        }
        cout<<n-dp[n%2][n]<<endl ;
    }
    return 0 ;
}