本文主要是介绍Partitioning by Palindromes UVA - 11584 （LIS/DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点下看看能不能打开：https://vjudge.net/problem/34398/origin
题目大意：输入小写字母字符串，然后分割成尽量少的回文串，例如：recacer本身就是回文串，fastcar只能分成7个，aaadbccb最少为3个为：aaa d bccb
ps:紫书p275
ps:记得以前做过关于回文串的dp，那个是比较复杂的了，属于区间dp的。
对于这个题的话，要求最少的回文串，那么就记录dp[j]表示前j个字符所能分割的最少回文串。那么如果出现i在j的后面，如果j+1~i是回文的话，那么就要比较dp[i]和dp[j]+1的大小去min；j是从0-i的
这里有一个预处理求区间[i,j]是否回文串的，详细见代码。为了方便处理，字符串从1开始的。
#include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3fusing namespace std;char s[1111];
int dp[1111];
int vis[1111][1111];int main()
{int t;scanf("%d",&t);while(t--){scanf("%s",s+1);int n=strlen(s+1);memset(vis,0,sizeof(vis));memset(dp,INF,sizeof(dp));///最大化for(int k=1;k<=n;k++){int i,j;i=k;j=k;while(i>0&&j<=n){if(s[i]==s[j]){vis[i][j]=1;i--;j++;}else break;}i=k;j=k+1;while(i>0&&j<=n){if(s[i]==s[j]){vis[i][j]=1;i--;j++;}else break;}}dp[0]=0;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(vis[j+1][i]){dp[i]=min(dp[i],dp[j]+1);}}}printf("%d\n",dp[n]);}return 0;
}
这篇关于Partitioning by Palindromes UVA - 11584 （LIS/DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
