Рекурсия: различия между версиями

Нет изменений в размере ,  11 лет назад
Если строка имеет вид <math>{h\; \alpha\; t}</math>, где <math>h</math> и <math>t</math> символы, а <math>\alpha</math> — подстрока, возможно пустая. Пусть <math>S(x)</math> — вычисляет минимальное количество символов, которые нужно убрать из строки <math>x</math>, чтобы оставшаяся строка была палиндромом.
 
Базой рекурсии являются строки из одного символа и пустая строка — все они полиндромыпалиндромы по определению, и для них <math>S = 0</math>. Шаг рекурсии состоит из двух частей:
 
<math>S(h\; \alpha\; t) = \begin{cases} S(\alpha), & h = t;\\ \min \Big( S(\alpha\, t) + 1,\; S(h\, \alpha) + 1,\; S(\alpha) + 2 \Big), & h \ne t. \end{cases}</math>
Анонимный участник