Задача из темы "Рекурсия, перебор", поэтому решим её через рекурсию, но также рассмотрим решение методом динамического программирования. Читаем условие:
Рекурсия
Разобьём нашу задачу размера N на подзадачи меньшего размера. Однако нельзя вычислить количество лесенок из N кубиков, зная ответы для меньшего числа, потому что они будут включать лесенки с одним кубиком на вершине (а такие лесенки никак не увеличить).
Поэтому подзадачи будут с двумя параметрами: сколько существует лесенок из N кубиков, чтобы верхний ряд содержал не меньше M.
Тогда, чтобы решить задачу для параметров N и M, надо перебрать все возможные варианты для верхнего ряда i (от M до N) и взять ответы для подзадач N - 1 и i + 1.
По сути, это уже и есть описание рекурсивной функции. Давайте её запишем:
Здесь мы добавили условие выхода из рекурсии: если N < M, то ответ 0, так как нам не хватает кубиков, чтобы заполнить даже верхний ряд.
Чтобы ужать решение (и сделать его менее читаемым), можно map и lamda заменить на генератор списка, а условие - на список из двух элементов:
Чтобы решение было полным, надо вызвать нашу функцию с правильными параметрами:
Однако это решение не укладывается в лимиты по времени. Есть несколько способов справиться с этим:
- запускать на PyPy
- добавить меморизацию
Динамическое программирование
Мы уже поняли, что в подзадачах понадобится два параметра. Но лесенку можно строить не снизу вверх, а сверху вниз. Тогда подзадача будет звучать так: сколько можно сделать лесенок из N кубиков, чтобы нижний ряд был не больше M.
Приведу пример заполнения таблицы для N = 9:
Исходя из описания подзадачи, понятно, что
d[M][N] = d[M - 1][N] + d[M - 1][N - M].
Первое слагаемое учитывает все лесенки с нижним рядом меньше M, а второе - с ровно M кубиками в нижнем ряду.
Получается, что каждый следующий ряд вычисляется из предыдущего. А значит всё можно провернуть в одном одномерном массиве. Главное - правильно выбрать направление движения по массиву. А именно, надо будет ходить справа налево.
Теперь у нас есть всё, чтобы написать решение:
Это решение и работает существенно быстрее, и потребляет памяти сильно меньше, чем рекурсивный вариант.
Предыдущий выпуск: Задача 752. 2-3 Дерево
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.