题面描述

塔子哥想构造一棵包含值为1到n的节点的二叉搜索树，并求出所有可能的不同二叉搜索树中，高度不超过k的数量。给定两个整数n和k（满足1 ≤ n, k ≤ 35），请输出符合条件的二叉搜索树的数量。例如，输入为5和4时，输出为26。

思路：动态规划/记忆化搜索

定义$cache[i][j]$有$i$个节点，并且树的高度不超过$j$的情况下，可以构造的二叉查找树的数量。

具体可以使用动态规划或者记忆化搜索来实现

初始状态为$cache[n][k]$，枚举到当前剩余节点个数为$m$时，我们可以分别枚举给左子树分配$[1:m]$个节点，右子树分配$[m-1:0]$个节点，并将对应的方案累乘，即为当前的方案数，累加当前方案数即为最终答案

为了避免重复计算，需要使用记忆化搜索

dfs(cnt, dep)函数表示当前有cnt个节点，树的高度为dep时，能构造出的二叉查找树的数量。

如果cnt为0，表示没有节点，那么只能构造出一棵空树，所以返回1。如果dep为0，表示树的高度已经超过了k，那么不能再构造出新的树，所以返回0。

初始状态

1. 基础情况：

   • 当节点数为 0 时，即 cnt == 0，返回 1，因为空树是唯一的。
   • 当高度 dep == 0 而节点数不为 0 时，返回 0，因为这表示树的高度已经超过了 $k$。

2. 状态转移：

   • 对于每个节点 $i$，可以选择作为根节点的值，然后分别将剩余的节点分配给左子树和右子树。左子树可以有 $[1:i]$ 个节点，右子树可以有 $[i-1:0]$ 个节点。
   • 对于每种选择，左右子树的组合数量相乘，然后累加到结果中。

代码

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std; 
const int N = 40; // 定义最大节点数
// cache数组，记录状态
int cache[N][N];

// 记忆化搜索函数，计算cnt个节点高度不超过dep的二叉搜索树数量
int dfs(int cnt, int dep) {
    // 如果当前状态已经计算过，直接返回结果
    if (cache[cnt][dep] != -1) return cache[cnt][dep];
    
    // 如果没有节点，则返回1（空树）
    if (cnt == 0) return 1;

    // 如果高度已经超出k，则返回0
    if (dep == 0) return 0;

    int res = 0; // 用于累计结果
    // 遍历每个节点作为根节点
    for (int i = 1; i <= cnt; ++i) {
        // 计算左子树和右子树的数量并累加
        res += dfs(i - 1, dep - 1) * dfs(cnt - i, dep - 1);
    }
    // 记录结果到cache数组
    return cache[cnt][dep] = res;
}

int main() {
    int n, k; // n为节点数，k为高度限制
    cin >> n >> k; // 输入n和k
    memset(cache, -1, sizeof cache); // 初始化cache数组为-1
    cout << dfs(n, k) << endl; // 输出结果
    return 0; // 程序结束
}

python代码

from functools import lru_cache

# 读取输入的节点数 n 和树的最大高度 k
n, k = map(int, input().split())

@lru_cache(maxsize=None)  # 使用 lru_cache 装饰器实现记忆化搜索，避免重复计算
def dfs(cnt, dep):
    # 如果当前没有节点，返回 1，因为空树是唯一的
    if cnt == 0:
        return 1
    # 如果当前深度小于等于 0，返回 0，因为无法构造树
    if dep <= 0:
        return 0
    
    ans = 0  # 初始化结果计数器
    # 遍历所有可能的根节点
    for i in range(cnt):
        # 递归计算左子树的数量，节点数为 i，深度减 1
        lc = dfs(i, dep - 1)
        # 递归计算右子树的数量，节点数为 cnt - i - 1，深度减 1
        rc = dfs(cnt - i - 1, dep - 1)
        # 累加左右子树的组合数量
        ans += lc * rc
    
    return ans  # 返回当前节点数和深度下的树的数量

# 输出从 n 个节点和最大深度 k 能构造的二叉搜索树的数量
print(dfs(n, k))

Java代码

import java.util.Scanner;

public class Main {
    static final int N = 40; // 定义常量 N，表示最大节点数
    static int[][] cache = new int[N][N]; // 创建二维数组 cache，用于存储已经计算过的结果

    // 深度优先搜索函数，计算在 n 个节点且高度不超过 k 的情况下可构造的树的数量
    static int dfs(int n, int k) {
        // 如果当前状态已计算过，直接返回结果
        if (cache[n][k] != -1) return cache[n][k];
        // 如果节点数为 0 且高度为 0，返回 1（表示空树）
        if (k == 0 && n == 0) return 1;
        // 如果节点数不为 0 但高度为 0，返回 0（无法构造树）
        if (k == 0 && n != 0) return 0;
        // 如果节点数为 0，返回 1（空树）
        if (n == 0) return 1;

        int res = 0; // 初始化结果计数器
        // 遍历所有可能的根节点
        for (int i = 1; i <= n; ++i) {
            // 递归计算左子树和右子树的组合数量
            res += dfs(i - 1, k - 1) * dfs(n - i, k - 1);
        }
        // 记录当前状态的结果到 cache 数组
        return cache[n][k] = res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象用于输入
        int n = scanner.nextInt(); // 读取节点数 n
        int k = scanner.nextInt(); // 读取树的最大高度 k
        
        // 初始化 cache 数组为 -1，表示尚未计算
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cache[i][j] = -1;
            }
        }

        // 输出从 n 个节点和最大深度 k 能构造的二叉搜索树的数量
        System.out.println(dfs(n, k));
    }
}