POJ1159回文字符串（DP+滚动数组）

题目的大概意思就是给你一个字符串，让你在任意位置添加任意字符让它变成一个回文字符串，求最少添加的字符数。

这是一道典型的DP，总体思路就是把逆串搞出来，两个字符串求出一个最大公共子序列的长度，然后拿n减去这个长度就可以了。

一开始想直接开二维的DP数组，结果发现5000的长度会爆。网上学了用一个滚动数组，因为当前状态只与上一状态有关，而且再先前的状态（上上状态）没有保存的意义。所以注意到0与1这两个数字能用1-x来进行互相转换，所以能大大节省内存的空间。以后感觉可能很有用。

代码如下：

//#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char str1[5005],str2[5005];
int maxlen[2][5005];
int main()
{
    int n;
    //freopen("de.txt","r",stdin);
    while (~scanf("%d",&n))
    {
        for (int i=1;i<=n;++i)
        {
            cin>>str1[i];
            str2[n+1-i]=str1[i];
        }
        str1[n+1]='\0';
        str2[n+1]='\0';
        memset(maxlen,0,sizeof maxlen);
        int e=0;//利用1-x，当x=0时1-x=1；x=1时1-x=0；
        for (int i=1;i<=n;++i)
        {
            e=1-e;//当前状态是e，有上一个状态1-e得出；
            for (int j=0;j<=n;++j)
            {
                if (str1[i]==str2[j])
                maxlen[e][j]=maxlen[1-e][j-1]+1;//相当于maxlen[i][j]=maxlen[i-1][j-1]+1
                else
                maxlen[e][j]=max(maxlen[e][j-1],maxlen[1-e][j]);//相当于maxlen[i][j]=max(maxlen[i][j-1],maxlen[i-1][j])
            }
        }
        cout<<n-maxlen[e][n]<<endl;//处理完成后当前状态是e，所以输出的是maxlen[e][n]
    }
    return 0;
}