UVA - 10617 Again Palindrome——dp

UVA - 10617 Again Palindrome——dp

求一个字符串有多少回文子串（可以不连续）

区间dp的无后效性思想，lcs的状态转移方程。。。。。。

定义dp【i】【j】为区间【i，j】的回文子串的数量

s【i】！=s【j】，dp【i】【j】 = dp【i+1】【j】+dp【i】【j-1】-dp【i+1】【j-1】

s【i】==s【j】，dp【i】【j】=dp【i+1】【j】+dp【i】【j-1】+1

感觉是从逻辑上推的状态转移方程，这方面还是不熟练

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 100;int T;char s[maxn];ll dp[maxn][maxn];int main() { scanf("%d", &T); getchar(); while (T--) { gets(s+1); int n = strlen(s+1); for (int i = 1; i <= n; i++) { dp[i][i] = 1; dp[i][i-1] = 0; } for (int len = 2; len <= n; len++) { for (int i = 1; i+len-1 <= n; i++) { int j = i+len-1; if (s[i] == s[j]) dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1; else dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]; } } cout << dp[1][n] << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。