题目链接:uva 11584 - Partitioning by Palindromes
题目大意:给出一个字符串,问说最少可以划分成几个回文串。
解题思路:dp[i]表示从1到第i个字符最少可以划分为几个回文,dp[i] = min{dp[j-1]+1 | judge(j,i) } ,judge函数判断从j到i是否可以形成回文串。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1005; const int INF = 0x3f3f3f3f; int n, dp[N]; char str[N]; bool judge(int l, int r) { while (l <= r) { if (str[l] != str[r]) return false; l++; r--; } return true; } int solve () { memset(dp, INF, sizeof(dp)); dp[0] = 0; scanf("%s", str+1); n = strlen(str+1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { if (judge(j, i)) dp[i] = min(dp[i], dp[j-1]+1); } } return dp[n]; } int main () { int cas; scanf("%d", &cas); while (cas--) { printf("%d\n", solve()); } return 0; }
uva 11584 - Partitioning by Palindromes(dp)
原文:http://blog.csdn.net/keshuai19940722/article/details/19850441