96. 不同的二叉搜索树#

1
给你一个整数 n ，求恰由 n 个节点组成且节点值
2

3
从 1 到 n 互不相同的 二叉搜索树 有多少种？
4

5
返回满足题意的二叉搜索树的种数。
6

7

8
示例 1：
9

10

11
输入：n = 3
12
输出：5
13
示例 2：
14

15
输入：n = 1
16
输出：1
17

18

19
提示：
20

21
1 <= n <= 19

1
class Solution {
2
public:
3
    int numTrees(int n) {
4
        vector<int> dp(n + 1, 0);
5
        dp[0] = dp[1] = 1;
6
        for(int i = 2; i <= n; i++)
7
        {
8
            for(int j = 1; j <= i; j++)
9
            {
10
                dp[i] += dp[j - 1] * dp[i - j];
11
            }
12
        }
13
        return dp[n];
14
    }
15
};