题目描述

给定一个 $n$，求共有多少种不同的 BST（二叉搜索树），满足中序遍历是 $1 … n$。

样例

输入：3
输出：5
解释：
给定 n = 3, 共有5种不同的二叉搜索树，如下所示：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

算法

(动态规划) $O(n^2)$

状态表示：$f[n]$ 表示 n个节点的二叉搜索树共有多少种。
状态转移：左子树可以有 $0, 1, … n-1$ 个节点，对应的右子树有 $n-1, n-2, …, 0$ 个节点，$f[n]$ 是所有这些情况的加和，所以 $f[n] = \sum_{k=0}^{n-1}f[k]*f[n-1-k]$。

时间复杂度分析：状态总共有 $n$ 个，状态转移的复杂度是 $O(n)$，所以总时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:
    int numTrees(int n) {
        vector<int>f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = 0;
            for (int j = 1; j <= i; j ++ )
                f[i] += f[j - 1] * f[i - j];
        }
        return f[n];
    }
};