주어진 문자열을 최소 개수의 팰린드롬으로 분할하는 경우 몇 개로 분할되는지 구하는 문제입니다. 문자열의 길이가 2500인 것으로 보아 $O(n^2\log{n})$ 이하의 시간 복잡도로 해결하라는 것 같습니다. 그 이전에 주어진 문자열의 특정 위치를 기준으로 얼마나 긴 팰린드롬이 생성되는지 구하는 것은 $O(n^2)$에 가능합니다. 그저 위치를 한 칸씩 옮겨가면서 문자가 같은지만 판별하면 됩니다.
이제 이것을 활용하여 몇 개의 팰린드롬으로 분할되는지 구할 수 있습니다. 시작점으로부터 길이가 k인 문자열을 잡았을 때 이것이 팰린드롬인지는 위에서 구한 값으로부터 유추할 수 있고, 만약 그렇다면 시작점에서 k 이동한 점을 새로운 시작점으로 하여 같은 행동을 반복하면 됩니다. 느낌상 재귀 함수를 만들고 하나의 매개 변수에 대한 리턴값은 DP 배열에 저장하면 될 것 같습니다. 이렇게 하면 $O(n^2)$에 해결이 가능하므로 도합 $O(n^2)$에 팰린드롬 분할의 개수를 구할 수 있습니다.
PS알못 OrbitHv의 PS