Разберём простую задачу на динамическое программирование, автором которой являюсь я сам - сочинил эту задачу для одного из контестов, а потом она попала в архив задач. Читаем условие:
Задача является сильным упрощением общего случая с разделением прямоугольника размера NxM, который надо решать с помощью динамического программирования по профилю. В этой же задаче можно поступить проще, рассмотрев все варианты.
Для начала считаем размер шоколадки:
Сразу можем обработать случай с нечётным N, так как тогда в шоколадке будет нечётное число плиток, и её нельзя будет разделить на кусочки по две плитки:
Очевидно, что состоянием в динамике будет длина шоколадки. Какие же есть переходы? Давайте нарисуем все варианты:
Во-первых, можно тремя способами отделить от шоколадки кусок 3х2, получив шоколадку размера 3xN-2.
Второй вариант - когда мы выходим за границы куска 3х2 (здесь, на самом деле два случая, которые симметричны друг другу). Тогда мы можем:
- либо ровно отделить кусок 3х4,
- либо снова выйти за его границы и продолжить рассуждения (отделить кусок 3х6 и так далее).
В приведённой формуле можно сделать небольшое преобразование:
2 * f(N - 2) тоже внесём в скобки (и всю скобку обозначим s), а одну f(N-2) оставим без изменений. Получим такой код:
На каждом шаге в r будет находиться ответ для шоколадки размера i, а в s будем накапливать удвоенную сумму всех предыдущих ответов.
И база динамики здесь - это шоколадка размера 3х2, для которой ответ известен.
Осталось вывести результат:
Таким образом, мы получили простое и лаконичное решение задачи без применения сложного алгоритма.
Предыдущий выпуск: Задача 296. Лиса Алиса и кот Базилио
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.