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