UniLecs #Task. Cubes
Задача: у вас есть одинаковые кубики. Из них можно построить двухсторонние лесенки.
В основании такой лесенки расположено N кубиков, а каждый следующий ряд кубиков укладывается на предыдущий таким образом, что один кубик укладывается ровно на один нижестоящий, а по крайней мере на самый правый и самый левый кубики предыдущего ряда новые кубики не кладутся (чтобы получилась ступенька).
Посчитайте сколько можно построить различных лесенок, состоящих из ровно K рядов кубиков, в основании которых лежит ровно N кубиков.
Примечание: если одну лесенку можно получить из другой путем зеркального отображения, то они все равно считаются различными.
Входные данные: N, K — числа, где 1 <= N <= 100, 1 <= K <= 100.
Вывод: кол-во различных лесенок.
Пример:
N = 10, K = 4;
Output: 84
Разбор
Задача решается двумерным динамическим программированием.
Пусть f(n,k) — количество пирамидок высоты k с основанием n. Тогда начальное значение: f(n,1)=1.
Рекуррентное соотношение — пусть требуется найти значение f(n,k). Основание пирамидки состоит из n кубиков, пронумеруем их числами от 1 до n. Теперь переберем основание второго ряда. Пусть номер левого кубика в основании второго ряда l, а номер правого кубика — r. Тогда двумя циклами перебираем значения: 2 ⩽ l ⩽ r ⩽ n−1.
К значению f(n,k) нужно добавить величину f(r−l+1, k−1) - количество пирамидок с основанием от l до r высоты k−1. Детали реализации смотрите ниже.
Реализация
https://gist.github.com/unilecs/fa14b0c68a82c0e462a9e1c8d3a50973
