смотрим на слово (1,n):
1. крайние буквы совпадают - берем все, что между ними, и решаем задачу для подслова (2,n-1)
2. разные - надо добавить либо слева, либо справа, решаем задачу для (1,n-1) и (2,n), выбираем минимальное
пока чистая рекурсия
сложность - что-то вроде порядка экспоненциальной (2^n)
при небольших n можно на этом остановиться
если хочется ускорить, замечаем, что слово (2,n-1) будет обрабатываться два раза:
1. после (1,n-1)
2. после (2,n)
вот и место для оптимизации
дальше, кстати, идет стандартная методика, которую можно применить в куче задач:
предположим, у нас есть реккурентный поиск чего-то оптимального
1. переделываем рекурсию в цикл с использованием стека
2. переделываем стек в очередь (что соответствует замене поиска в глубину поиском в ширину)
3. начинаем отсеивать элементы при добавлении в очередь
в нашем случае это выглядит так:
1. делаем очередь из троек чисел: (начало подслова, конец подслова, значение критерия
2. ставим туда (1,n,0)
3. цикл
3.1. берем очередной элемент очереди
3.2. если буквы совпадают, добавляем в очередь (начало+1, конец-1, критерий - не изменился)
3.3. если буквы разные
3.3.1. добавляем в очередь (начало+1, конец, критерий+1)
3.3.2. добавляем в очередь (начало, конец-1, критерий+1)
4. когда остались только одиночные символы, выбираем тот, у которого меньше критерий
!!!пока сложность осталась экспоненциальной!!!
добавляем правило отсева:
процедура добавления элемента в очередь:
1. если элемента с такими началом и концом нет в очереди - просто добавляем
2. если есть - смотрим, какой критерий меньше, минимум записываем в этот элемент - остается опять один элемент с, возможно, уменьшившимся критерием
после этого сложность уже не превышает количества всевозможных пар (начало, конец) - N^2 (в смысле порядка)...