Алгоритм для задачи

[dreamkiller]

Дана задача по программированию
Дана строка S, состоящая из$ n (1 ≤ n ≤ 300)$ маленьких латинских букв. За один ход Вам разрешается удалить один или несколько подряд идущих одинаковых символов. Необходимо удалить все символы из строки S за минимальное количество ходов.

Я использовал следующий алгоритм для её решения.
1)Все подряд идущие одинаковые меняем на 1 символ.
2) В строке находим два одинаковых символа, чтобы между ними было минимально возможное число других символов.
3)Удаляем все символы между найденными. К количеству ходов добавляем количество удаленных символов.
4) повторяем 1-3 до тех пор, пока каждый символ в строке не станет уникальным(то есть встречаться только раз).
5)К количеству ходов прибавляем количество оставшихся символов.

Проблема в том, что алгоритм не всегда срабатывает. Помогите привести пример, не работающий на данном алгоритме и более правильный алгоритм для решения.

[venco]

Алгоритм пока не придумал, но ваш неправильно обработает строку "adecabcfgb".

-- Ср фев 22, 2012 10:18:55 --

Вроде динамическое программирование сработает.
Параметры - номер первого и последнего символов подстроки, которая удаляется независимо от других символов. В этой подстроке первый символ может либо удалятся один, либо совместно с другим таким-же (если он есть). Во втором случае все несовпадающие символы между ними должны удалятся независимо. Возможны детали, но идея должна сработать.

[dreamkiller]

А если в алгоритм добавить такой шаг:
Если символ в строке встречается 1 раз удаляем его и прибавляем к числу операций 1(Используем перед первым шагом.)?

-- 22.02.2012, 18:27 --

venco в сообщении #541625 писал(а):

Алгоритм пока не придумал, но ваш неправильно обработает строку "adecabcfgb".

-- Ср фев 22, 2012 10:18:55 --

Вроде динамическое программирование сработает.
Параметры - номер первого и последнего символов подстроки, которая удаляется независимо от других символов. В этой подстроке первый символ может либо удалятся один, либо совместно с другим таким-же (если он есть). Во втором случае все несовпадающие символы между ними должны удалятся независимо. Возможны детали, но идея должна сработать.

А поподробнее? Вообще, эта задача идет по теме "рекурсии".