Задача на деревья и думаю DP

[frankenstein]

Задача звучит так:
Фермер Джон хочет купить стадо коров. В новом стаде каждая корова
родит ровно 2х коровят ). Родственные связи между коровами могут
быть легко продемонстрированы бинарным деревом с N вершинами. Эти
деревья обладают таким свойством:
1. Степень каждой вершины 0 или 2. Степень - это количество непосредственных потомков.
2. Высока дерева ровно K. Высота это максимальное количество узлов из корня до листьев.
Листья это вершины у которых нет детей.

Сколько сущесвует разных деревьев у которых N вершин, и высота которых равна K. Деревья
различаются по структуре.
Например:
При N=5 и K=3, ответ равен 2.



Не знаю как подобраться к задаче.
Пробовал решать перебором, строил по очереди деревья, но получилось
очень очень медленно.

[Foxer]

Да, это динамика. Вспомните, как решается задача о количестве правильных скобочных последовательностей динамически. Сначала мы ищем кол-во правильных скобочных последовательностей длины до $(2n - 2)$ включительно, а затем перебираем положения первой открывающей и соответствующей ей закрывающей скобке и подсчитываем ответ для $2n$.

То что я написал нужно приспособить к деревьям и понять, как подсчитать деревья не любой высоты, а только заданной.

[frankenstein]

Да, точно ведь дерево можно представить как скобочную последовательность.
Тогда, кажется, деревья из примера будут в виде:

$( ( ( ) ( ) ) ( ) )$

$( ( ) ( ( ) ( ) ) )$

Значит надо посчитать точное количество разных скобочных последовательностей
c 2N скобками, где максимальная вложенность равна K?

[Foxer]

Не совсем так, ибо, хотя бы насколько я понял, коров всегда нечетное число, а скобок всегда четное. Во-вторых, если уж так рассуждать, то первой открывающей должна соответствовать последняя скобка, иначе будут коровы, не являющиеся потомками первой.
Не пытайтесь в программировании мыслить как математик. Не нужно сводить задачу к уже решенной, как в математике. Так вы не постигните дзена DP. Есть общие приемы, которые стоит усвоить, а далее идет индивидуальная специфика каждой задачи.

Я подсказал вам, что нужно думать аналогично. Насчет отслеживания глубины деревьев - тут как вы организуете динамику. Мне представляется, что ответ будет лежать в $k$-ой ячейке таблицы динамики, т.е. нужно считать не просто "сколько правильных деревьев я могу построить", а "сколько правильных деревьев глубины $m$ я могу построить". Да, работать это будет медленней, но что-то вы с ограничениями задачи промолчали.

[frankenstein]

Ограничения на входные данные
$2 < N < 200$

$1 < K <100$

[Foxer]

Нормально, у меня получается оценка $O(N^2K)$, что обычные компьютеры считают в пределах одной секунды.

[frankenstein]

Foxer в сообщении #870589 писал(а):

Нормально, у меня получается оценка $O(N^2K)$, что обычные компьютеры считают в пределах одной секунды.

Спасибо, у меня тоже получилось )