本文主要是介绍uva 11584 Partitioning by Palindromes | dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=465&page=show_problem&problem=2631
算是刚开始认真做dp吧，觉得dp真的好神奇，而且在做之前的省赛题（浙江）时，总能发现一两道是dp。虽说这题是在看了别人的思路下写出来的，不过对我而言，还是益处很大的，写写博客，加深印象！
题意：
给你一个字符串，让你求出最小的回文段数。
思路：
dp[i]表示在第i个字母时加入时最小的回文段数。
可以用这个方程进行转移：dp[i] = min(dp[i],dp[j-1]+1);j的范围[1,i]；
意思是：如果从j到i是回文，那么dp[i]的回文段数等于j-1前的回文段数加上1；
AC代码：
<span style="font-size:18px;">#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int P = 1005;
char tmp[P];
int dp[P];
bool Charge(int i,int j)
{int mid = (i+j)/2;while(j<=mid){if(tmp[j++] != tmp[i--])return 0;}return 1;
}
int main()
{int T;cin>>T;while(T--){scanf("%s",tmp+1);memset(dp,-1,sizeof(dp));dp[0] = 0;int len = strlen(tmp+1);for(int i = 1;i <= len;i++){for(int j = 1;j <= i;j++){if(dp[i] == -1)dp[i] = dp[i-1]+1;if(Charge(i,j)){dp[i] = min(dp[i],dp[j-1]+1);}}}cout<<dp[len]<<endl;}return 0;
}</span>*其实感觉是UVa数据有点弱，这个如果换作变态点数据，可能就TLE了。后来把字符串(1...len)预处理判断回文，但时间跑得更久了...
这篇关于uva 11584 Partitioning by Palindromes | dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
