BOJ 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

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

코드