huawei2023112903

Problem Description

Given an integer ( n ), construct binary search trees with nodes labeled from 1 to ( n ). Determine the number of unique binary search trees with a height not exceeding ( k ) (where the root node is considered to have a height of 1).

Input Description

• Two integers ( n ) and ( k ), where ( 1 $\leq$ n, k $\leq$ 35 ).

Output Description

• An integer representing the number of unique binary search trees.

Example

Input:

5 4

Output:

26

Approach

Define ( cache[i][j] ) as the number of binary search trees (BSTs) that can be constructed with ( i ) nodes and a height not exceeding ( j ).

This can be implemented using dynamic programming and memoized search.

Steps are as follows:

1. Base Cases:

   • If ( k ) is 0 and ( n $\neq$ 0 ), it means the tree height has exceeded ( k ). Thus, no tree can be constructed, so return 0.
   • If ( k ) is 0 and ( n ) is also 0, it means there are no nodes and the height is 0. Hence, only one empty tree can be constructed, so return 1.
   • If ( n ) is 0, it means there are no nodes, so only one empty tree can be constructed, but k not 0,so return 1.

2. Recursive Calculation:

   • For each ( n ), distribute ( [1
     ] ) nodes to the left subtree and ( [n-1:0] ) nodes to the right subtree. The number of ways to construct the BST is the product of the ways to construct each subtree. Sum these products to get the total number of BSTs for the current configuration.

3. Memoized Search:

   • To avoid redundant calculations, use memoized search. Define a function dfs(cnt, dep) that returns the number of BSTs that can be constructed with cnt nodes and a height of dep.
   • If the result for dfs(cnt, dep) has been computed previously, return the cached result directly.

import java.util.Scanner;public class Main {    // Define the maximum size for cache    static final int N = 40;    // Initialize cache for memoization k<=35    static int[][] cache = new int[N][N];    // Depth-first search function for memoization    static int dfs(int n, int k) {        // If the result for (n, k) is already calculated, return it directly from cache(memory search)        if (cache[n][k] != -1) return cache[n][k];        // Base cases        if (k == 0 && n == 0) return 1; // If both k and n are 0, return 1 as there's only one empty tree        if (k == 0 && n != 0) return 0; // If k is 0 but n is not, return 0 as it's impossible to construct a tree        if (n == 0) return 1; // If n is 0, return 1 as there's only one empty tree        int res = 0;        // Recursively calculate the number of BSTs        for (int i = 1; i <= n; ++i) {            res += dfs(i - 1, k - 1) * dfs(n - i, k - 1);// (i-1)+x = n-1 => x = n-i        }        // Cache the result for (n, k)        return cache[n][k] = res;    }    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        // Read input values for n and k        int n = scanner.nextInt();        int k = scanner.nextInt();        // Initialize cache with -1        for (int i = 0; i < N; i++) {            for (int j = 0; j < N; j++) {                cache[i][j] = -1;            }        }        // Calculate and print the result        System.out.println(dfs(n, k));    }}