Задача из раздела комбинаторика, но на мой взгляд - это в чистом виде динамическое программирование. Давайте разбираться: Давайте посмотрим на последний ряд дерева. Понятно, что все листья разбиваются на группы по 2 или 3. Научимся считать количество разбиений методом динамического программирования. База динамики: 2, 3 и 4 элемента разбиваются единственным способом.
Шаг динамики, если все ответы до i элементов посчитаны: какой могла быть последняя группа? Всё те же 2 или 3 элемента, то есть ответ для задачи размера i складывается из ответов для подзадач размера i - 2 и i - 3...
В технике, экономике и некоторых других направлениях иногда приходится решать задачи на поиск оптимального пути или состояния. По сути это цель любой автоматизации - минимизировать затраты или получить наилучший результат. Это понятие ввёл в 40-ых годах прошлого века Ричард Беллман. Идея достаточно простая - для того чтобы получить конечный результат, необходимо предварительно решить несколько вспомогательных задач. Решить каждую из которых можно решив их предварительные задачи. Саму постановку...