Unique Binary Search Trees

题目描述：

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

思路:

数学题

代码:

func numTrees(n int) int {
    res := make([]int, n+1)
    res[0] = 1
    res[1] = 1
    for i:=2; i<=n ;i++{
        for j:=1; j<=i;j++{
            res[i] += res[j-1] * res[i-j]
        }
    }
    return res[n]
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了87.51%的用户