本文主要是介绍hdu 4632——Palindrome subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dp
可能出现负数，注意加mod再%mod。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 10007
int dp[1100][1100];
char s[1100];
int len;
int dfs(int l,int r)
{
if(dp[l][r]!=-1)
return dp[l][r];
if(r-l==1)
if(s[l]==s[r])
return dp[l][r]=3;
else
return dp[l][r]=2;
if(s[l]==s[r])
dp[l][r]=dfs(l+1,r)+dfs(l,r-1)+1;
else
dp[l][r]=dfs(l+1,r)+dfs(l,r-1)-dfs(l+1,r-1);
dp[l][r]=(dp[l][r])%mod;
return dp[l][r];
}
int main()
{
int t;
int cnt=1;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
memset(dp,-1,sizeof(dp));
len=strlen(s);
for(int i=0;i<len;i++)
dp[i][i]=1;
dfs(0,len-1);
printf("Case %d: %d\n",cnt++,dp[0][len-1]);
}
return 0;
}
这篇关于hdu 4632——Palindrome subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
