096.md

Unique Binary Search Trees

题目

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example: Input: 3 Output: 5 Explanation:

Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

总结：
	给定一个数n,n的结果为当root分别为1~n组成的所有结果。如果x属于区间[1,n]则 x为root那么1~x-1组成的bst的数量left 乘以 x+1到n组成的bst的数量right 即为x为root有的bst数量。
	有两个区间分别为[x1,x2],[y1,y2]如果x2-x1==y2-y1那么两个区间组成的bst数量相同。

代码

func numTrees(n int) int {
    mp := make(map[int]int, 0)
    mp[1] = 1
    left , right := 0, 0
    for i := 2; i <= n; i++ {
        count := 0
        for j := 1; j <= i; j++ {
            left, right = mp[j-1],  mp[i-j]
            if left == 0 {
                left = 1
            } 
            if right == 0 {
                right = 1
            }
            count += left * right
        }
        mp[i] = count
    }
    return mp[n]
}