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

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;
    }
}

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 和 计算一次 bst >h。这种技术的另一个优点是，一旦表被填满，bst 将在 O(1) 中响应(对于表范围内的值)。请注意不要使用高于 MAX_H 和 MAN_N 的值调用该函数。另请记住，记忆化是一种内存时间权衡，这意味着您的程序将运行得更快，但也会使用更多内存。

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