删除若干个字母后 剩下的是回文串 求有多少个
记忆化搜索 dp[i][j]表示i j 之间有多少个 其实递推也可以的 long long
#include#include long long dp[70][70]; char a[70]; long long n; long long dfs(long long l,long long r) { if(l > r) return 0; if(l == r) return 1; if(dp[l][r] != -1) return dp[l][r]; long long ret = 0; if(a[l] == a[r]) { ret = dfs(l+1,r) + dfs(l,r-1) + 1; //ret = dfs(l+1,r) + dfs(l,r-1) - dfs(l+1,r-1)+ dfs(l+1,r-1) + 1; } else { ret = dfs(l+1,r) + dfs(l,r-1) - dfs(l+1,r-1); } dp[l][r] = ret; return ret; } int main() { long long t; scanf("%lld",&t); while(t--) { scanf("%s",a+1); n = strlen(a+1); memset(dp,-1,sizeof(dp)); printf("%lld\n",dfs(1,n)); } return 0; }