-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution96.java
More file actions
38 lines (31 loc) · 1.4 KB
/
Copy pathSolution96.java
File metadata and controls
38 lines (31 loc) · 1.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution96 {
public static void main(String[] args) {
final Solution96 s = new Solution96();
System.out.println(s.numTrees(1));
System.out.println(s.numTrees(2));
System.out.println(s.numTrees(3));
System.out.println(s.numTrees(4));
System.out.println(s.numTrees(5));
}
public int numTrees(int n) {
// 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则
// G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
// 当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
// f(i) = G(i-1)*G(n-i)
// 综合两个公式可以得到 卡特兰数 公式
// G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
// 作者：guanpengchn
// 链接：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/hua-jie-suan-fa-96-bu-tong-de-er-cha-sou-suo-shu-b/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j]; // 从 1 开始的左右子树之和的乘积加起来
}
}
return dp[n];
}
}