I. Разрезание на палиндромы

Разрежьте строку на наименьшее число кусков так, чтобы каждый кусок был палиндромом. Выведите количество кусков.

Здесь две динамики, и обе нужны.

Одна строка длины $n$ ($1 \le n \le 5000$) из строчных латинских букв.

Одно число - наименьшее количество палиндромных кусков.