hdu 1513 dp +优化

//我个人的理解就是当前行的结果只与前一行的结果有关
//所以每次枚举行的时候滚动数组的行%2；
//就只有0,1，两种状态 也就是两行交替存储答案 。。。就这样的 不然内存不够用的哦
#include<iostream>
#include<string>
using namespace std;
int ans[3][5005];
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
int main()
{
    int i,j,n;
    char s1[5005],s2[5005];
 // freopen("E:\\test.txt","r",stdin);
    while(cin>>n)
    {
        cin>>s1;
        for(i=0;i<n;i++)
        {
            s2[i]=s1[n-i-1];
        }
  s2[n]='\0';
 // cout<<s1<<endl<<s2<<endl;
        memset(ans,0,sizeof(ans));
        for(i=0;i<n;i++)
        {
            ans[0][i]=0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(s2[j-1]==s1[i-1])
                {
                    ans[i%2][j]=ans[(i-1)%2][j-1]+1;
                }
                else
                {
                    ans[i%2][j]=max(ans[(i-1)%2][j],ans[i%2][j-1]);
                }
            }
        }
        cout<<n-ans[n%2][n]<<endl;
    }
    return 0;
}