UVA 11584 - Partitioning by Palindromes DP

題目大意：

輸入一個由小寫字母組成的字符串，你的任務是把它劃分成盡量少的回文串。比如，racecar本身就是回文串，fastcar只能分為7個單字母組成的回文串；aaadbccb最少可以分成3個回文串：aaa、d、bccb。字符串長度不超過1000

思路：

設dp[i]為到達下標i劃分的最少回文串。

則dp[i]=min{ dp[j-1]+1 }( j from 1 to i) 即如果 j 到 i 是回文串，那麼等於最少為dp[j-1]+1

#include
#include
#include
using namespace std;
const int MAXN=1024;
const int INF=0x7fffffff;
int dp[MAXN];
char s[MAXN];
bool ok(int i,int j)
{
	while(i