zoj 1700 二叉搜索树

这道题目是一道经典的二叉搜索树问题，需要用到二叉搜索树的性质来解决。

首先，我们可以将问题转化为求解 $n$ 个节点构成的二叉搜索树的数量。假设 $F(n)$ 表示 $n$ 个节点构成的二叉搜索树的数量，那么对于任意一个节点 $i$，它可以作为树的根节点，将这个二叉搜索树分成左右两棵子树，左子树有 $i-1$ 个节点，右子树有 $n-i$ 个节点。因此，我们可以得到以下递归式：

$$F(n) = \sum_{i=1}^{n} F(i-1) \times F(n-i)$$

边界条件为 $F(0) = 1$，因为空树也是一棵二叉搜索树。

接下来，我们可以使用动态规划的方式来求解 $F(n)$。具体思路是从 $F(0)$ 开始，逐步计算出 $F(1), F(2), \cdots, F(n)$。在计算 $F(n)$ 时，需要依赖已经计算出来的 $F(0), F(1), \cdots, F(n-1)$。最终的答案即为 $F(n)$。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。代码如下：