【基础题目】96. 不同的二叉搜索树

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

解题思路：动态规划
这道题很容易绕晕，但我们要学会抓住本质。

1、分析

⭕ 问题：假设现在有 n 个点，要求dp[n]，即n个点能构造多少种二叉搜索树。
● 可以进行如下分类思考：
 ● 当以 1 为根节点时，能构造出多少种；
 ● 当以 2 为根节点时，能构造出多少种；
 ● 当以 3 为根节点时，能构造出多少种；
 ● ……
 ● 当以 n 为根节点时，能构造出多少种；
如果我们知道了上述的各个种类数，可以通过相加求解。

● 关键是我们如何知道以 i 为根节点时，能够造出多少种二叉搜索树呢？——根据左、右子树再分类！
  ● 左子树能构造出多少种
  ● 右子树能够造出多少种
如果我们知道了上述左右子树的种类数，我们就可以通过相乘，求得以 i 为根节点时能构造的二叉搜索种类数。

● 左子树（右子树）的种类数怎么求呢？——如果我们知道了左子树（右子树）的节点数为m，又知道dp[m]（m个节点能够造的二叉搜索树种类），那么问题就迎刃而解了。
而动态规划，就是从小规模到大规模的利器！

2、动态规划步骤

(1) dp数组定义：dp[i] 表示 i 个点能够造的二叉搜索树种类数；

(2) 递推公式：dp[i] += dp[j - 1] * dp[i - j]（ 以 j 为根节点，j-1 为左子树的节点数，i-j 为右子树的节点数）

(3) 初始化：dp[0] = 1
● 从定义入手：0个节点的空树，也是一个二叉搜索树
● 从递推式入手：以 j 为根节点的树中，如果左子树为空，右子树不为空，那么二叉搜索树种类数显然不能为0，那么就需要保证相乘的时候dp[左子树个数] = 1。

(4) 遍历顺序：从小规模到大规模，因此是从1到n

(5) 举例：
 当 i == 3时：
  当以 1 为根节点时，能构造出dp[0] * dp[2]种；
  当以 2 为根节点时，能构造出dp[1] * dp[1]种；
  当以 3 为根节点时，能构造出dp[2] * dp[0]种；
 因此：dp[3] = dp[0] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

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