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