HDU - 4632 - Palindrome subsequence（区间DP）

本文主要是介绍HDU - 4632 - Palindrome subsequence（区间DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4632

题意：找一个字符串里有多少个回文子序列。

思路：和最长回文子序列差不多， $dp[i][j]$ 表示第 $i$ 个字符到第 $j$ 个字符回文子序列的个数， $dp[i][i]$ 初始化为1，题目给出单个字符也是一个回文子序列。 $dp[i][j]$ 前一个状态有两个 $dp[i+1][j]$ 和 $dp[i][j-1]$ ，很明显要这两个相加，但是 $dp[i+1][j]$ 和 $dp[i][j-1]$ 相加有一段重复了，因为这两个都包含 $dp[i+1][j-1]$ ，故而减去一个，所以第一个状态转移方程： $dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]$ ；然后当字符串 $s[i]==s[j]$ 时，即这两个字母相同，那么就是和 $dp[i+1][j-1]$ 状态的回文组成新的回文序列，所以第二个状态转移方程就是： $dp[i][j]=dp[i][j]+dp[i+1][j-1]+1$ 。注意负数取模。

/****   █████▒█    ██  ▄████▄   ██ ▄█▀       ██████╗ ██╗   ██╗ ██████╗* ▓██   ▒ ██  ▓██▒▒██▀ ▀█   ██▄█▒        ██╔══██╗██║   ██║██╔════╝* ▒████ ░▓██  ▒██░▒▓█    ▄ ▓███▄░        ██████╔╝██║   ██║██║  ███╗* ░▓█▒  ░▓▓█  ░██░▒▓▓▄ ▄██▒▓██ █▄        ██╔══██╗██║   ██║██║   ██║* ░▒█░   ▒▒█████▓ ▒ ▓███▀ ░▒██▒ █▄       ██████╔╝╚██████╔╝╚██████╔╝*  ▒ ░   ░▒▓▒ ▒ ▒ ░ ░▒ ▒  ░▒ ▒▒ ▓▒       ╚═════╝  ╚═════╝  ╚═════╝*  ░     ░░▒░ ░ ░   ░  ▒   ░ ░▒ ▒░*  ░ ░    ░░░ ░ ░ ░        ░ ░░ ░*           ░     ░ ░      ░  ░*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 7;
const int mod = 1e4 + 7;
int dp[N][N];
char s[N];
int main()
{int T, Cas = 1; scanf("%d%*c",&T);while(T--){scanf("%s%*c", s+1); int n = strlen(s + 1);memset(dp, 0, sizeof dp);for(int i = 1; i <= n; i++)dp[i][i] = 1;for(int l = 2; l <= n; l++){for(int i = 1; i + l - 1 <= n; i++){int j = i + l - 1;if(s[i] == s[j]) dp[i][j] = (dp[i+1][j] % mod + dp[i][j-1] % mod + 1) % mod;else dp[i][j] = (dp[i+1][j] % mod + dp[i][j-1] % mod - dp[i+1][j-1] + mod) % mod;}}printf("Case %d: %d\n",Cas++, dp[1][n]);}}

这篇关于HDU - 4632 - Palindrome subsequence（区间DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！