UVa11584Partitioning by Palindromes(字符串区间dp)
题意：给定一个字符串s, 问说最少可以划分成几个回文串。
思路：dp[i]表示从1到第i个字符最少可以划分为几个回文，状态转移方程
dp[i] = min(dp[i], dp[j-1]+1), 如果满足 s[j] 到 s[i] 为回文字符串。
用 judge 函数判断从j到i是否可以形成回文串。
Sample Input
3
racecar
fastcar
aaadbccb
Sample Output
1
7
3
<span style="font-size:18px;">#include <cstdio>#include <iostream>#include <cstring>#include <cmath>#include <string>#include <algorithm>#include <queue>#include <stack>using namespace std;const double PI = acos(-1.0);const double e = 2.718281828459;const double eps = 1e-8;const int MAXN = 1010;char s[MAXN];int dp[MAXN];int judge(int l, int r){while(l <= r){if(s[l] != s[r])return 0;l++;r–;}return 1;}int main(){//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int Case;cin>>Case;while(Case–){scanf("%s", s+1);int len = strlen(s+1);dp[0] = 0;for(int i = 1; i <= len; i++)dp[i] = 1010;for(int i = 1; i <= len; i++){for(int j = 1; j <= i; j++){if(judge(j, i))dp[i] = min(dp[i], dp[j-1]+1);}}cout<<dp[len]<<endl;}return 0;}</span>
，，再回头，便生出无限羁绊。那是彼此的刺在对方心里留下的痕迹，
