题目内容

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示

1 <= n <= 19

题解

本题因为仅求方案数，且可以通过求解子问题递推出最终答案，因此采用动态规划方法求解。

1、状态表示：F(n)表示n个节点的二叉搜索树的方案数量

2、状态转移：左子树可能有0,1,2, … , n-1个节点，对应的右子树有n-1,n-2,n-3, … , 个节点，F(n)是上述全部情况的加和。

即：F[n] = ΣF(k) x F(n-1-k) ,k从0到n-1。

代码

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