首页 > 代码库 > Light OJ 1025 - The Specials Menu（动态规划-区间dp）
Light OJ 1025 - The Specials Menu（动态规划-区间dp）
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1025
题目大意：一串字符， 通过删除其中一些字符， 能够使这串字符变成回文串。 现在给你一串字符，问能够得到多少种不同的回文串；
注意：字符串"abba", 可以得到9串回文串，分别为‘a‘, ‘a‘, ‘b‘, ‘b‘, ‘aa‘, ‘bb‘, ‘aba‘, ‘aba‘, ‘abba‘.
解题思路：声明dp[i][j]为字符串[i,j]区间中通过删除可以得到不同回文串的数量
那么有以下两种情况：
1：当str[i] != str[j]时， dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]; （之所以减去dp[i+1][j-1] 是前面两项多加了一个dp[i+1][j-1]）
2：当str[i] == str[j]时， dp[i][j] = (dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]) + (dp[i+1][j-1] + 1);（前面一项是指str[i]和str[j]不对应时能够组成回文串的方案数，第二项是指str[i]和str[j]对应时能够组成回文串的方案数）
需要注意的不能第一项直接循环i， 第二项直接循环j， 那么求dp[i][j]时，dp[i+1][j] 可能还没求得正确的值。
dp数组代码如下：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int INF = 0x3f3f3f3f;const int N = 103;ll dp[N][N];char str[N];void solve(int cases){ scanf("%s", str); int l = strlen(str); memset(dp, 0, sizeof(dp)); for(int i=0; str[i]; ++ i) dp[i][i] = 1; for(int len=1; len<l; ++ len) { for(int i=0; i+len<l; ++ i) { int j=i+len; if(str[i] != str[j]) dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]; else dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1; } } printf("Case %d: %lld\n", cases, dp[0][l-1]);}int main(){ int T; scanf("%d", &T); for(int i=1; i<=T; ++ i) solve(i); return 0;}
记忆化搜索代码如下：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int INF = 0x3f3f3f3f;const int N = 103;ll dp[N][N];char str[N];ll dfs(int l, int r){ if(l == r) return dp[l][r] = 1; if(dp[l][r] != -1) return dp[l][r]; if(l > r) return 0; ll ans; if(str[l] != str[r]) ans = dfs(l, r-1) + dfs(l+1, r) - dfs(l+1, r-1); else ans = dfs(l, r-1) + dfs(l+1, r) + 1; return dp[l][r] = ans;}void solve(int cases){ scanf("%s", str); int l = strlen(str); memset(dp, -1, sizeof(dp)); printf("Case %d: %lld\n", cases, dfs(0,l-1));}int main(){ int T; scanf("%d", &T); for(int i=1; i<=T; ++ i) solve(i); return 0;}
Light OJ 1025 - The Specials Menu（动态规划-区间dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。