1044 - Palindrome Partitioning PDF (English) Statistics ForumTime Limit: 1 second(s) Memory Limit: 32 MBA palindrome partition is the partitioning of a string such that each separate substring is a palindrome.
For example, the string "ABACABA" could be partitioned in several different ways, such as {"A","B","A","C","A","B","A"}, {"A","BACAB","A"}, {"ABA","C","ABA"}, or {"ABACABA"}, among others.
You are given a string s. Return the minimum possible number of substrings in a palindrome partition of s.
InputInput starts with an integer T (≤ 40), denoting the number of test cases.
Each case begins with a non-empty string s of uppercase letters with length no more than 1000.
OutputFor each case of input you have to print the case number and the desired result.
Sample InputOutput for Sample Input3AAAAABCDEFGHQWERTYTREWQWERTCase 1: 1Case 2: 8Case 3: 5
解题:预处理好回文字符串，然后dfs。
但dp[l][r] = min(dp[l][r],dfs(l,i)+dfs(i+1,r)); 这种的dfs会爆
仔细分析下会发现 (回文字符串+一串字母) + 一串字母 跟 回文字符串+(一串字母+一串字母) 的情况是一样， 所以可能省略掉前面dfs(l,i)的情况
直接 if(judge[l][i]) dp[l][r] = min(dp[l][r],1+dfs(i+1,r));
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int inf = 1e9; int T,len; char str[1100]; int dp[1100][1100]; bool judge[1100][1100]; void init(){ memset(judge,false,sizeof(judge)); memset(dp,-1,sizeof(dp)); for(int i=0;i<len;i++){ for(int j=i;j<len;j++){ int flag = 0; for(int z=i;z<=(i+j)/2;z++){ if(str[z]!=str[j-(z-i)]){ flag = 1;break; } } if(flag == 0) judge[i][j] = true; } } } int dfs(int l,int r){ if(judge[l][r]){ dp[l][r] = 1; return 1; } if(dp[l][r]!=-1) return dp[l][r]; dp[l][r] = inf; for(int i=l;i<r;i++){ if(judge[l][i]) dp[l][r] = min(dp[l][r],1+dfs(i+1,r)); //dp[l][r] = min(dp[l][r],dfs(l,i)+dfs(i+1,r)); } return dp[l][r]; } int main(){ scanf("%d",&T); for(int t=1;t<=T;t++){ scanf("%s",str); len = strlen(str); init(); printf("Case %d: %d\n",t,dfs(0,len-1)); } return 0; } View Code
转载于:https://www.cnblogs.com/yuanshixingdan/p/5540692.html
相关资源：JAVA上百实例源码以及开源项目