2. Палиндром

Задача на динамическое программирование. Сначала необходимо построить таблицу `T`, в которой в ячейке `T[i,j]` хранится минимальное количество добавляемых символов к строке `s[i…j]` для получения палиндрома. `T[i,j]\ =\ T[i+1,j-1]`, если `s[i]=s[j]`, `T[i,j]\ =\ min(T[i,j-1],T[i+1,j])\ +\ 1` если `s[i]≠s[j]`. Выполняя обратную трассировку по таблице `T` легко найти палиндром-результат. "Жадное" частичное решение, выполняющее анализ строки одновременно слева и справа и добавляющее в результат меньший из концов в случае несовпадения, дает 15 баллов.