96. Unique Binary Search Trees

题目

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

题意

给定一个整数n，求有多少种结构的二叉搜索树来存储1..n的整数值

例子

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

题解

我们遍历1~n,遍历到的元素作为根，然后就拆分为左右两个子树，分别时0~i,i+1~n,由于都是递增的，所以以当前节点i为根的结构总数就为dp[i]*dp[n-i]，遍历所以元素作为根的情况，求其总和就能得到dp[n]。

代码

var dp []int
func numTrees(n int) int {
    dp = make([]int,n+1)
    return CountUB(n)
}

func CountUB(n int)int{
    if n<=0{
       return 0
    }
    
    if dp[n]!=0{
        return dp[n]
    }
    
    count:=0
    for i:=1;i<=n;i++{
        l:=CountUB(i-1)
        r:=CountUB(n-i)
        if l==0{
            l=1
        }
        if r==0{
            r=1
        }
        count=count+(l*r)
    }
    dp[n]=count
    return count
}
}

总结

递归+dp解决。其实解决这道题的思路关键在于意识到以谁为根之后，左右两边的子树个数为多少个。只要个数相同，且为递增，则不管值为多少，他们的结构数目都是相同的。查了这道题的资料，发现竟然还出来一个卡塔兰数，有点时间看看。