hdu 4632 Palindrome subsequence

http://acm.hdu.edu.cn/showproblem.php?pid=4632

简单DP

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<list>
using namespace std;

typedef long long ll;
typedef pair<double,double>ppd;
const double PI = acos(-1.);
const double eps = (1e-9);
const int MOD=10007;
const int N=1005;
char s[N];
int ans[N][N];
int dp(int l,int r)
{
    if(ans[l][r]!=-1)
    return ans[l][r];//记忆化
    ans[l][r]=0;
    if(l==r)//边界
    return (ans[l][r]=1);
    if(l+1==r)//边界
    {
        ans[l][r]=2;
        if(s[l]==s[r])
        ++ans[l][r];
        return ans[l][r];
    }
    if(s[l]==s[r])//以l和r 为左右端点的情况 其中的1表示的是单独的l和r也是一个回文
    ans[l][r]+=dp(l+1,r-1)+1;
    ans[l][r]+=(dp(l+1,r)+dp(l,r-1)-dp(l+1,r-1));//把多加的减掉
    ans[l][r]%=MOD;
    if(ans[l][r]<0)
    ans[l][r]+=MOD;
    return ans[l][r];
}
int main()
{
    //freopen("data.in","r",stdin);
    int T;
    scanf("%d",&T);
    for(int c=1;c<=T;++c)
    {
        scanf("%s",s);
        memset(ans,-1,sizeof(ans));
        printf("Case %d: %d
",c,dp(0,strlen(s)-1));
    }
    return 0;
}