给定高度的二叉搜索树数量

Question

如何找出给定高度 h 的所有BST的数量，并且在给定唯一数字集合中丢弃高于h的所有BST？

我已经使用递归方法编写了代码。

static int bst(int h,int n){
    if(h==0&&n==0)return 1;
    else if(h==0&&n==1)return 1;
    else if(h==0&&n>1)return 0;
    else if(h>0&&n==0)return 1;
    else{
        int sum=0;
        for(int i=1;i<=n;i++)
            sum+=bst(h-1,i-1)*bst(h-1,n-i);
        return sum;
    }
}

- Aman Arora

---

动态规划，一如既往。 - David Eisenstat

例如，对于4个节点，二叉搜索树的数量为14。但是如果我们想将树的高度限制为3，那么树的数量现在会减少。 - Aman Arora

@DavidEisenstat 你能解释一下吗？ - Aman Arora

按照高度和节点数对表进行索引。 - David Eisenstat

@DavidEisenstat，我在动态规划方面没有太多经验。你能建议适当的更改吗？记忆体的索引是什么？ - Aman Arora

Answer 1

根据评论中@DavidEisenstat的建议，您可以通过添加备忘录来加速它。

您可以创建一个备忘录表来存储已经计算出结果的值。在示例中，-1表示该值尚未计算。

c++示例:

long long memo[MAX_H][MAX_N];

long long bst(int h,int n){
    if(memo[h][n] == -1){
        memo[h][n] = //Compute the value here using recursion
    }
    return memo[h][n];
}

...

int main(){
    memset(memo,-1,sizeof memo);
    bst(102,89);
}

这将以O(h*n)的时间执行，因为您只会为每个可能的n和h对计算一次bst。这种技术的另一个优点是，一旦填满表格，bst将在O(1)时间内响应（对于表格范围内的值）。

请注意不要使用大于MAX_H和MAN_N的值调用函数。还要记住，记忆化是一种内存和时间的权衡，这意味着您的程序将运行得更快，但它也会使用更多的内存。

更多信息：https://en.wikipedia.org/wiki/Memoization

- jspurim