Как я должен реализовать метод рекурсии, чтобы найти количество способов формирования максимальной кучи в C++?

Question

Если dp[n] хранит количество способов формирования максимальной кучи, содержащей n элементов, то мы имеем.

dp[n] = nCr(n - 1, n1) * dp[n1] * dp[n2];

т.е.

1. Выберите n1 элементов из n - 1 для левого поддерева.

2. Элементы в левом поддереве могут образовывать максимальную кучу dp[n1] способами.

3. Элементы в правом поддереве могут образовывать максимальную кучу dp[n2] способами.

Как рассчитать n1 и n2?

Answer 1

Я полагаю, что вам не хватает цикла, который включает в себя формулу, которую вы опубликовали. Вы меняете n1 от 1 через n-1, Если "максимальная куча" требует, чтобы вы потребляли все n узлы, то у вас есть просто n2 = n-n1, Если вы можете использовать меньше, то вам нужен другой цикл для изменения n2 от 1 через n-n1,

Вернуть сумму всех этих вычисленных величин.