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

Question

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

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

IE

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

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

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

如何计算n1和n2？

Answer 1

我相信您缺少包含您发布的公式的循环。你n1从1到变化n-1。如果“最大堆”要求您消耗所有n节点，那么您只需n2 = n-n1. 如果您可以使用更少，那么您需要另一个循环来n2从1到n-n1。

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