Число двоичных деревьев поиска заданной высоты

Question

Как найти количество BST до заданной высоты h и отбросить все BST с высотой больше h для заданного набора уникальных чисел?

Я разработал код, используя рекурсивный подход

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 предложил в комментариях.

Вы создаете таблицу memoization для хранения значений уже вычисленных результатов. В этом примере -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), как вы будете только вычислить bst один раз для каждой возможной пары n и h. Другим преимуществом этого метода является то, что после заполнения таблицы bst ответит на O (1) (для значений в диапазоне таблицы). Будьте внимательны, чтобы не вызвать функцию со значениями выше MAX_H и MAN_N. Также имейте в виду, что memoization - это компромисс между памятью, то есть ваша программа будет работать быстрее, но она также будет использовать больше памяти.

Подробнее: https://en.wikipedia.org/wiki/Memoization