Pavlunchik
23.12.2006 21:55
Здравствуйте помогите пожалуйсто решить задачу про ПАЛИНДОМ
условие такое
вводится строка и надо узнать какое количество символов надо убрать из строки что бы она стала полиндромом
Помогите пожалуйсто очень надо!!!
можете писать на мsло
<censored> задача разумеется на паскале
М |
|
1. Здесь не доска объявлений! 2. Темы разделила - незачем заниматься некрофилией. мисс_граффити
|
Michael_Rybak
24.12.2006 21:10
Решается динамическим программированием. Функцию f(i, j) определим так: f(i, j) - это решение задачи для подстроки с символа i по символ j. Рекуррентное соотношение:
f(i, j) = 0, если j <= i + 1
f(i, j) = f(i + 1, j - 1), если s[i] = s[j]
f(i, j) = min(f(i + 1, j), f(i, j - 1)) в оставшихся случаях