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]
}