96. Unique Binary Search Trees
Medium
Given an integer
n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.Example 1:
Input: n = 3
Output:
5
Example 2:
Input: n = 1
Output:
1
Constraints:
1 <= n <= 19
以不同的點當作中點，以 5 為例，左右子樹可能有以下情況：
左 | 右 | sum |
|---|---|---|
0 | 4 | 14 |
1 | 3 | 5 |
2 | 2 | 4 |
3 | 1 | 5 |
4 | 0 | 14 |
合計 42 種可能
func numTrees(n int) int {
if n == 1 { return 1 }
dp := []int{1, 1}
for i:=2; i<=n; i++ {
sum := 0
for j:=0; j<i; j++ {
sum += dp[j] * dp[i - 1 - j] // 左子樹種類乘以右子樹種類
}
dp = append(dp, sum)
}
return dp[n]
}