我应该如何实现递归方法以找到在C++中形成最大堆的多种方法

Question

如果 dp[n] 存储了形成包含 n 个元素的最大堆的方法的数量，那么我们就有了。

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

即

1. 从 n - 1 中选择 n1 个元素作为左侧子树。

2. 左子树中的元素可以以 dp[n1] 的方式形成最大堆。

3. 右子树中的元素可以以 dp[n2] 方式形成最大堆。

如何计算 n1 和 n2？

Answer 1

我相信

您错过了包含您发布的公式的循环。 您n1从1到n-1各不相同。 如果"最大堆"要求您使用所有n节点，那么您只需n2 = n-n1 . 如果您可以使用更少，则需要另一个循环来改变从1到n-n1 n2。

返回所有这些计算数量的总和。