Как я должен реализовать метод рекурсии, чтобы найти количество способов формирования максимальной кучи в C ++?
Если dp [n] хранит количество способов формирования максимальной кучи, содержащей n элементов, то мы имеем.
dp[n] = nCr(n - 1, n1) * dp[n1] * dp[n2];
то есть
-
Выберите n1 элементов из n — 1 для левого поддерева.
-
Элементы в левом поддереве могут образовывать максимальную кучу dp [n1] способами.
-
Элементы в правом поддереве могут образовывать максимальную кучу dp [n2] способами.
Как рассчитать n1 и n2?
Решение
Я полагаю, что вам не хватает цикла, который включает в себя формулу, которую вы опубликовали. Вы меняете n1 от 1 через n-1, Если «максимальная куча» требует, чтобы вы потребляли все n узлы, то у вас есть просто n2 = n-n1, Если вы можете использовать меньше, то вам нужен другой цикл для изменения n2 от 1 через n-n1,
Вернуть сумму всех этих вычисленных величин.
Другие решения
Других решений пока нет …