1509 - 팰린드롬 분할

https://www.acmicpc.net/problem/1509

$dp$[$i$] = $i$번째 위치에서 가능한 팰린드롬 분할의 최소 개수
$isPaline$[$i$][$j$] = $i$~$j$ 가 팰린드롬인가

예제에도 끼워져있지만 AABDBADD 와 같은 경우의 처리때문에 여러 경우를 탐색해야한다. 이것을 분할하는 경우는 아래와 같다.

A - A - B - D - B - A - D - D
A - A - B - D - B - A - DD
A - A - BDB - A - D - D
A - A - BDB - A - DD
A - ABDBA - D - D
A - ABDBA - DD
AA - B - D - B - A - D - D
AA - B - D - B - A - DD
AA - BDB - A - D - D
AA - BDB - A - DD

팰린드롬으로 최대한 묶은 후, 남은 문자열에 대해서 이 작업을 반복한다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

bool isPaline[2501][2501];
int dp[2501];

int solve(int pos){
    if(pos < 0) return 0;
    int& r = dp[pos];
    if(r != -1) return r;
    r = INF;
    for(int i=pos; i>=0; --i){
        if(isPaline[pos][i]){
            r = min(r, 1+solve(i-1));
        }
    }
    return r;
}

int main(){
    memset(dp, -1, sizeof(dp));
    char s[2501];
    scanf("%s", s);
    int len=strlen(s);
    for(int i=0; i<len; ++i){
        isPaline[i][i] = true;
        for(int j=0; j<i; ++j){
            if(s[i]==s[j]) isPaline[i][j] = isPaline[i-1][j+1];
            // 짝수인 경우 처리
            if(i-j==1) isPaline[i][j] |= s[i]==s[i-1];
        }
    }
    printf("%d", solve(len-1));
    return 0;
}