<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
We say a sequence of characters is a palindrome if it is the same written forwards and backwards. 
For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not. 
A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. 
For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups. 
Given a sequence of characters, 
we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: 
what is the minimum number of groups needed for a given string such that every group is a palindrome 
For example: 
‘racecar’ is already a palindrome, therefore it can be partitioned into one group. 
‘fastcar’ does not contain any non-trivial palindromes, so it must be partitioned as (‘f’, ‘a’, ‘s’, ‘t’, ‘c’, ‘a’, ‘r’). 
‘aaadbccb’ can be partitioned as (‘aaa’, ‘d’, ‘bccb’).
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 
1000 lowercase letters, with no whitespace within.
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
For each test case, output a line containing the minimum number of groups required to partition the 
input into groups of palindromes.
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
3 
racecar 
fastcar 
aaadbccb
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
1 
7 
3
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
求最少的划分,使所有部分都是回文串
最初的想法是:尽可能长的划分每一部分,最后输出答案 
这样有一个问题就是 <code>bcbaabc</code> 答案应该是 <code>2</code> 但是输出会是 <code>4</code> 
局部不取最优反而能使结果最优
类似于 贪心 与 背包 的关系 
因此换用 动态规划 
还是仿照上面的思路 
有 <code>dp[i] = min{dp[j-1] + 1}</code> ( <code>j~i</code> 是回文串)
写到这很容易,但是最后 <code>WA</code> 了好几发 
问题在于 边界值 
由于字符串从 <code>0</code> 开始 
因此循环的时候 <code>j-1</code> 有可能为 <code>-1</code> 
这是一个随机的值,本地测试的时候可能会是 <code>0</code> 输出正确答案,但是交上去后就只能看脸了
要解决也很简单 
从 <code>1~len</code> 循环 
判断回文串的时候将位置坐标减去 <code>1</code> 即可
时间复杂度是 <code>O(n3)</code> 
不过大多数情况最后一个循环(判断回文串)是立即结束的
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cmath&gt;
#include &lt;cstring&gt;
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;string&gt;
#include &lt;vector&gt;
#include &lt;bitset&gt;
#include &lt;functional&gt;

using namespace std;

const int maxn = 1005;

int dp[maxn];
string s;

bool isPalindrome(int a,int b) {
 for(int it1 = a,it2 = b;it1 &lt; it2;it1++,it2--)
 if(s[it1] != s[it2])
 return false;
 return true;
}

void Do() {
 cin &gt;&gt; s;
 int len = s.size();
 int ans = 0;

 dp[0] = 0;
 for(int i = 1;i &lt;= len;i++) {
 dp[i] = dp[i - 1] + 1;
 for(int j = 1;j &lt; i;j++)
 if(isPalindrome(j - 1,i - 1))
 dp[i] = min(dp[i],dp[j - 1] + 1);
 }

 cout &lt;&lt; dp[len] &lt;&lt; endl;
}

int main() {
 int T;
 cin &gt;&gt; T;
 for(int i = 1;i &lt;= T;i++)
 Do();
 return 0;
}
</pre>

Uva 11584.Partitioning by Palindromes