题面描述

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

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

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

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

题目描述

定义二叉搜索树为满足如下性质的特殊二叉树：

• 若其左子树不为空，则左子树上所有结点的值均小于其根结点的值；
• 若其右子树不为空，则右子树上所有结点的值均大于其根结点的值；

若满足以上条件，则称该二叉树的左右子树分别为二叉查找树。

给定一个整数 $n$，小明想构造一棵二叉查找树，由值为 $1$ 到 $n$ 的结点构成，请你帮小明求出所有能够构造出的不同二叉查找树中，高度不超过 $k$ 的数量。（根节点高度为 $1$）

输入描述

两个整数 $n$ 和 $k$，满足 $1 \le n, k \le 35$。

输出描述

一个整数，表示答案。

5 4

26