本文共 856 字,大约阅读时间需要 2 分钟。
题意:给你一个字符串,让你找出回文串的最少个数
题解:查询当前字符与前面字符子串是否构成回文串,如果构成则 dp[i] = min(dp[i],dp[j-1]+1);
#include#include #include using namespace std;int dp[1005];char str[1005];bool find(int k,int r){ while(k < r) { if(str[k] == str[r]) k++,r--; else return false; } return true;}int main(){ int n,Case = 1;; scanf("%d",&n); getchar(); while(n--) { scanf("%s",str); int l = strlen(str); for(int i = 0; i < l; i++) { dp[i] = i + 1; for(int j = 0; j <= i; j++) { if(find(j,i)) { if(j == 0) dp[i] = 1; else dp[i] = min(dp[i],dp[j - 1] + 1); } } } printf("Case %d: %d\n",Case++,dp[l-1]); }}
转载地址:http://lfsgi.baihongyu.com/