UniLecs #Task. String Cutting
Задача: дана строка s. Разрешена следующая операция: взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. И в самом начале вы также можете выбрать любое количество символов в строке и удалить их.
Необходимо определить наименьшее количество символов, которое вам потребуется удалить в самом начале, чтобы затем выполняя разрешенную операцию, получить пустую строку.
Входные данные: s — строка, размер строки от 1 до 100.
Вывод: наименьшее количество символов, которое следует удалить сначала.
Пример: s = “abbcddka” (сначала необходимо убрать 2 символа “c” и “k”, дальше последовательно убираем пары “bb”, “dd”, “aa” и получаем пустую строку)
Output: 2
Разбор
Итак воспользуемся методом динамического программирования.
Пусть d[l, r] - наименьшее кол-во символов, которое следует удалить из подстроки s(l)...s(r), чтобы далее можно было получить пустую строку, путем операции удаления одинаковых соседних символов.
Очевидно, что
- d[l, r] = 0, если l > r.
- d[l, l] = 1.
- d[l, r] = d[l + 1, r - 1], если s(l) = s(r). То есть если крайние символы одинаковы, то следует удалить внутреннюю часть, после чего эти символы станут соседними и их можно будет удалить с помощью заданной операции одинаковых соседним символов.
- d[l, r] = 1 + d[l + 1, r]. То есть если мы удаляем 1й символ.
- d[l, r] = 1 + d[l, r - 1]. То есть если мы удаляем последний символ.
Два последних условия можно объединить в следующее: для решения на отрезке [l, r] разделим задачу на две подзадачи на отрезка [l, i] и [i + 1, r], где (l <= i <= r) и возьмем наименьший результат.
d[l, r] = Min(d[l, i] + d[i + 1, r]), где l <= i <= r.
Для строки длины N, ответом будет d[0, N - 1].
Реализация
https://gist.github.com/unilecs/2d930448985c677cd328d9572a0f3928
