H. Дописать до палиндрома

Сколько символов нужно вставить в строку (в любые места), чтобы она стала палиндромом?

Ответ - $n$ минус длина наибольшей палиндромной подпоследовательности.

Почему: символы, входящие в палиндромную подпоследовательность, уже стоят зеркально, и их можно не трогать. Для каждого из остальных достаточно вставить его зеркальную копию.

Обратное тоже верно: если вставили $k$ символов, то из полученного палиндрома длины $n + k$ можно выбросить вставленные и получить подпоследовательность исходной строки длины $n$... но она может не быть палиндромом. Аккуратное доказательство идёт по индукции, и его стоит проделать - это ровно та задача, где «очевидно» подводит.

Считать заново ничего не надо: это классная задача плюс одно вычитание.

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

Одно число - наименьшее количество вставок.