leetcode 链接：96. 不同的二叉搜索树

题目

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

示例：

输入：n = 3
输出：5

输入：n = 1
输出：1

解答 & 代码

因为是二叉搜索树，因此序列 [1,2,....,n] 就是二叉搜索树的中序遍历的结果。可以以该序列中任意一个位置 i 作为根节点，那么左边就是左子树的中序序列，右边就是右子树的中序序列。以 i 作为根节点的二叉搜索树个数 = 长为 i - 1 的二叉搜索树的个数（左子树的种数） * 长为 n - i 的二叉搜索树的个数（右子树的种数）。而长为 n 的二叉搜索树的总个数，就是以各个位置 i 作为根节点的二叉搜索树个数的总和

动态规划：

• 设置 dp 数组，dp[i] 代表长度为 i 的序列能构成的不同二叉搜索树的个数
• 状态转移：

• 初始化：dp[0] = 1, dp[1] = 1

  class Solution {
  public:
    int numTrees(int n) {
        if(n < 0)
            return -1;
  
        // 动态规划，dp[i] 代表长度为 i 的序列能构成的不同二叉搜索树的个数
        vector<int> dp(n + 1, 0);
        // 初始化
        dp[0] = 1;
        dp[1] = 1;
        // 状态转移
        for(int i = 2; i <= n; ++i)        // 长为 i 的序列对应的二叉搜索树个数 = 以每个元素为根节点的不同二叉搜索树个数之和
        {
            for(int j = 1; j <= i; ++j)    // 以 j 为根节点的不同二叉搜索树个数为左右子树种数的乘积
                dp[i] += dp[j - 1] * dp[i - j];
        }
        return dp[n];
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗：5.9 MB, 在所有 C++ 提交中击败了 47.79% 的用户 ```