// 區間dp import java.util.Scanner;/**** @author CN*/ public class main {static int mod = 10007;static String l;static int[][] dp = new int[1010][1010];public static void main(String[] args){// TODO code application logic hereint t;Scanner sc = new Scanner(System.in);t = sc.nextInt();for(int i=1;i<=t;i++){ l = sc.next();for(int p=0;p<1010;p++){for(int q=0;q<1010;q++)dp[p][q] = 0;}for(int r=0;r<l.length();r++)dp[r][r] = 1;for(int len = 1;len<l.length();len++){for(int p=0;p<l.length();p++){for(int q=p+len;q<l.length();q++){dp[p][q] = dp[p+1][q] + dp[p][q-1];if(l.charAt(p)!=l.charAt(q))dp[p][q]-=dp[p+1][q-1];else dp[p][q]++;dp[p][q]=(dp[p][q]+mod)%mod; break;}}}System.out.println("Case "+i+": "+dp[0][l.length()-1]); }} }

import java.util.Scanner; // 記憶化搜索寫法public class Main {static int mod = 10007;static String l;static int[][] dp = new int[1010][1010];static int dfs(int le,int rt){if(le>rt)return 0;if(le==rt)return 1;if(dp[le][rt]!=-1)return dp[le][rt];dp[le][rt] = (dfs(le+1,rt)+dfs(le,rt-1) - dfs(le+1,rt-1)+ mod)%mod;if(l.charAt(le)==l.charAt(rt))dp[le][rt] = (dfs(le,rt)+dfs(le+1,rt-1)+1)%mod;return dp[le][rt];}public static void main(String[] args){int t;Scanner sc = new Scanner(System.in);t = sc.nextInt();for(int i=1;i<=t;i++){ l = sc.next();for(int p=0;p<l.length();p++){for(int q=0;q<l.length();q++)dp[p][q] = -1;} System.out.println("Case "+i+": "+dfs(0,l.length()-1)); }} }

題意就是在一個字符串計數任意可能的回文子串 計算所有子串的數量 每個字串要求先后順序相同
思路: 也就是根據子串的左右邊界定義一個子串用dp[i][j]表示從i到j的所有的回文子串的數量 分析可知 dp[i][j] 可以由兩個狀態轉移得來 也就是dp[i+1][j] 和 dp[i][j-1]之和得來 如果i處的字符不等于j處的字符 需要減去一個公共部分dp[i+1][j-1] 因為以上兩個狀態中的任意一個狀態都會包含這個狀態的 信息 所以會多一個dp[i+1][j-1] 不妨減去 如果i字符等于j處字符 也就是可以構成一個新的回文子串 這個數量關系 仍然是dp[i-1][j-1]得來 或者使用記憶化搜索去做 一開始可以把所有值初始化為一個不可能值 比如-1如果這個值搜索到的時候非-1 也就是已經搜索過了 可以直接返回

注意有減法的取模操作 +mod 再%mod 一開始Case后面多了個# WA了好幾發 。。?？影　！！?

總結

以上是生活随笔為你收集整理的Palindrome subsequence HDU - 4632 区间dp|记忆化搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。