本文主要是介绍hdu - 4632 - Palindrome subsequence（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求一个给定字符串的回文子串个数（字符串长度 <= 1000，共T（T <= 50）组测试数据，不同位置的相同回文串算不同的）。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4632
——>>设d[i][j]表示区间[i, j]内的回文子串个数，
状态转移方程：d[i][j] = (d[i+1][j] + d[i][j-1] - d[i+1][j-1]) % mod;
如果两端字符相同，则加上以两端字符为两端的回文子串个数，这时只要(i, j)内出现回文串，加上两端也肯定是回文串，所以这种回文子串的个数为d[i+1][j-1]。
注意：因为取模，状态转移方程的计算可能出现负数！
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 1000 + 10;
const int mod = 10007;
int d[maxn][maxn];
char S[maxn];int main()
{int T, kase = 1, i, j, k;scanf("%d", &T);while(T--){scanf("%s", S);int len = strlen(S);memset(d, -1, sizeof(d));for(i = 0; i < len; i++) d[i][i] = 1;for(i = 0; i < len-1; i++) d[i][i+1] = S[i] == S[i+1] ? 3 : 2;for(k = 2; k < len; k++){for(i = 0; i+k < len; i++){j = i + k;d[i][j] = (d[i+1][j] + d[i][j-1] - d[i+1][j-1]) % mod;if(d[i][j] < 0) d[i][j] += mod;if(S[i] == S[j]) d[i][j] = (d[i][j] + d[i+1][j-1] + 1) % mod;}}printf("Case %d: %d\n", kase++, d[0][len-1]);}return 0;
}
记忆化搜索写法，C++843ms，G++TLE：
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 1000 + 10;
const int mod = 10007;
int d[maxn][maxn];
char S[maxn];int dp(int i, int j){int& ans = d[i][j];if(ans != -1) return ans;if(i + 1 == j){if(S[i] == S[j]) return ans = 3;else return ans = 2;}if(i == j) return ans = 1;if(S[i] == S[j]) ans = dp(i+1, j-1) + 1;else ans = 0;ans = (ans + dp(i, j-1) + dp(i+1, j) - dp(i+1, j-1)) % mod;if(ans < 0) ans += mod;return ans;
}int main()
{int T, kase = 1;scanf("%d", &T);while(T--){scanf("%s", S);int len = strlen(S);memset(d, -1, sizeof(d));printf("Case %d: %d\n", kase++, dp(0, len-1));}return 0;
}
这篇关于hdu - 4632 - Palindrome subsequence（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
