Паліндром.
Паліндром - слово, яке читається з обох сторін однаково. Скласти програму, яка перетворює у паліндром довільне слово, викреслюючи з нього мінімальну кількість букв. Словом будемо вважати послідовність маленьких літер алфавіту.
Це - класична задача динамічного програмування.
Нехай задано послідовність символів:
X=(q,w,e,r,t).
Утворимо нову послідовність:
Y=(t,r,e,w,q),
записавши символи заданої послідовності ззаду наперед. Знайдемо довжину найбільшої спільної послідовності.
Якщо розв'язувати задачу "в лоб", перебираючи всі можливі підпослідовності послідовності Х та перевіряючи для кожної з них, чи не буде вона підпослідовністю послідовності Y, то алгоритм буде правильним, але неефективним.
Візьмемо матрицю A[0..Length(X), 0..Length(Y)], у якій будемо зберігати довжину спільної послідовності. Будемо порівнювати і-й елемент послідовності Х з кожним елементом послідовності Y і заповнюватимемо матрицю А за таким правилом:
Покажемо заповнення матриці на прикладі тесту з умови задачі:
Таким чином, у клітинці А[m,m] записано загальну довжину найбільшої спільної послідовності. Для знаходження мінімальної кількості символів, яку потрібно вилучити, достатньо від загальної кількості символів відняти довжину найбільшої спільної послідовності.