hdu-4632-Palindrome subsequence-記憶化dp

題意：

給你一個字符串，問你這個字符串最多含有多少個回文字串

做法：

dp[l][r]:  l到r這一段字符串含有的回文串的個數。

如果l==r：dp[l][r]=dps(l+1,r-1)+1+(dps(l+1,r)+dps(l,r-1)-dps(l+1,r-1));

否則：      dp[l][r]=(dps(l+1,r)+dps(l,r-1)-dps(l+1,r-1));

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define P 10007
char str[1001];
int dp[1001][1001];
int dps(int l,int r)
{
    if(dp[l][r]!=-1)return dp[l][r];
    if(l==r)
    {
        dp[l][r]=1;
        return 1;
    }
    if(l+1==r)
    {
        if(str[l]==str[r])dp[l][r]=3;
        else dp[l][r]=2;
        return dp[l][r];
    }
    dp[l][r]=0;
    if(str[l]==str[r])dp[l][r]=dps(l+1,r-1)+1;
    dp[l][r]+=(dps(l+1,r)+dps(l,r-1)-dps(l+1,r-1));
    dp[l][r]=dp[l][r]%P;
    if(dp[l][r]<0)dp[l][r]+=P;
    return dp[l][r];
}
int main()
{
    int T;
    scanf("%d%*c",&T);
    int  t=T;
    while(T--)
    {
        gets(str);
        int n;
        n=strlen(str);
        int i,j;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                dp[i][j]=-1;
            }
        }
        printf("Case %d: %d\n",t-T,dps(0,n-1));
    }
    return 0;
}