Динамическое программирование

Сегодня решим сложную задачу на динамическое программирование про поиск уникальных подпоследовательностей. Читаем условие: Сложность задачи складывается из нескольких пунктов: Напомню, что подстрока - это непрерывная последовательность символов с i-го до j-го. Или, на языке Python - это слайс s[i:j]. А подпоследовательность - это любая последовательность, которая может быть получена из исходной вычёркиванием произвольного числа символов. Количество подстрок O(N^2), а количество подпоследовательностей O(2^N), поэтому перебрать все не получится...

Давно не было решений на С++. Сегодня разберём непростую задачу на динамическое программирование по подмножествам, которую на Python затолкать в ограничения очень сложно. Читаем условие: Почти всегда, когда в задаче есть перебор перестановок, можно решение за O(N!) заменить решением за O(N * 2^N), используя динамическое программирование по подмножествам. Это всё ещё экспоненциальное решение, но константа сильно меньше. В нашем случае, если решать задачу в лоб, то надо каждую перестановку ещё проверять на удовлетворение условий К-перестановки...

Разберём решение ещё одной задачи на динамическое программирование, в которой нет ничего сложного, и можно рассмотреть все шаги решения таких задач. Сначала читаем условие: Алгоритм решения будет точно таким же, как и в задачах Задача 11. Зайчик и Задача 29. Компьютерная игра. Но здесь есть дополнительные ограничения, поэтому рекомендую разобраться с теми задачами и потом вернуться сюда. Как обычно, сначала надо определиться, что будет состоянием динамики. Выберем в качестве состояния длину префикса введённого числа...

Разберём простую задачу на динамическое программирование, автором которой являюсь я сам - сочинил эту задачу для одного из контестов, а потом она попала в архив задач. Читаем условие: Задача является сильным упрощением общего случая с разделением прямоугольника размера NxM, который надо решать с помощью динамического программирования по профилю. В этой же задаче можно поступить проще, рассмотрев все варианты. Для начала считаем размер шоколадки: Сразу можем обработать случай с нечётным N, так как...

Рассмотрим простую задачу на динамическое программирование, в которой построение ответа почти в два раза больше, чем само решение. Читаем условие: Задача не является продолжением или вариацией задачи 16. Лесенка, но решать будем тоже с помощью динамики. Считаем входные данные и сразу преобразуем их к числовым типам: Состоянием в динамическом программировании будет номер ступеньки, на которой стоит Вова. Чтобы узнать переходы, надо ответить на вопрос "Как Вова мог здесь оказаться?". Ответ очень простой - или с предыдущей ступеньки или через одну от неё...

Очень классная задача на динамическое программирование, в которой надо ещё придумать, как быстро посчитать результат. Читаем условие: Идея динамического программирования лежит на поверхности - чтобы вычислить стоимость для N надо знать стоимость для S и N - S (и правильно распределить, к чему прибавить 1, а к чему - 2). Получаем одномерную динамику - ответ зависит лишь от количества элементов в множестве. База динамики: для 1 ответ 0. Если загаданное число среди одного, то не надо задавать вопросов, чтобы узнать, что это за число...