96. 不同的二叉搜索树
题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
实例1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
方法：动态规划
定义两个函数：
- $G(n)$：长度为
n的序列能构成的不同二叉搜索树的个数。 - $F(i,n)$：以
i为根、长度为n的不同二叉搜索树的个数($1<=i<=n$)。
可见，$G(n)$是我们求解需要的函数。
不同的二叉搜索树的总数 $G(n)$，是对所有 $i(i<=i<=n)$ 的 $F(i,n)$ 之和。
\(G(n)= \sum_{i=1}^{n}F(i,n)\)
当序列长度为 1（只有根）或为 0（空树）时,
\(G(0)=1, G(1)=1\)
另外，根为 1 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积.
举例而言，创建以 $3$ 为根、长度为 $7$ 的不同二叉搜索树，整个序列是 $[1, 2, 3, 4, 5, 6, 7]$，我们需要从左子序列 $[1, 2]$ 构建左子树，从右子序列 $[4, 5, 6, 7]$ 构建右子树，然后将它们组合（即笛卡尔积）。
对于这个例子，不同二叉搜索树的个数为$ F(3, 7)$。我们将 $[1,2]$ 构建不同左子树的数量表示为 $G(2)$, 从 $[4, 5, 6, 7]$ 构建不同右子树的数量表示为$ G(4)$，注意到 $G(n)$ 和序列的内容无关，只和序列的长度有关。于是，$F(3,7) = G(2) \cdot G(4)$。所以，我们可以得到以下公式： \(F(i,n) = G(i-1) \cdot G(n-1)\) 将公式$(1), (3)$结合可以得到： \(G(n) = \sum_{i=1}^{n}G(i-1) \cdot G(n-1)\) 至此，我们从小到大计算 $G$ 函数即可，因为 $G(n)$ 的值依赖于 $G(0) \cdots G(n-1)$。
/**
* 96. 不同的二叉搜索树
*
* @param n
* @return
*/
public int numTrees(int n) {
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}