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

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            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<