UVa11584 Partitioning by Palindromes

이 문제는 한 줄이 최소한 몇 개의 회문열로 구성되었는지 판단해야 한다.자서상의 사고방식에 따라 먼저 각 구간이 회문열인지 아닌지를 미리 처리한다.그리고 dp0~i의 해를 제거한다.dp는 정말 가장 유연한 사상입니다!

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    
#define INF 1000000  
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
  
using namespace std;  

bool isP[1010][1010];
int dp[1010];

int main(){
	int t;
	cin>>t;
	char str[1010];
	
	while(t--){
		memset(isP,0,sizeof(isP));
		
		cin>>str;
		int len=strlen(str);
		for(int i=0;i<len;i++){
			for(int j=0;i-j>=0&&i+j<len;j++){
				if(str[i+j]!=str[i-j])break;
				isP[i-j][i+j]=true;
			}
		}
		for(int i=0;i<len;i++){
			for(int j=1;i-j+1>=0&&i+j<len;j++){
				if(str[i+j]!=str[i-j+1])break;
				isP[i-j+1][i+j]=true;
			}
		}
		
		dp[0]=0;
		for(int i=1;i<=len;i++){
			dp[i]=INF;
			for(int j=0;j<=i;j++){
				if(isP[j][i-1])(dp[i]=min(dp[i],dp[j]+1));
			}
		}
		
		cout<<dp[len]<<endl;
	}
	return 0;
}