H. Наибольшая палиндромная подпоследовательность

Найдите длину наибольшей подпоследовательности строки, являющейся палиндромом. Подпоследовательность получается вычёркиванием любых символов, порядок остальных сохраняется.

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

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