096._unique_binary_search_trees.md

###96. Unique Binary Search Trees

题目: https://leetcode.com/problems/unique-binary-search-trees/

难度: Medium

思路：

参照此处hint:

https://shenjie1993.gitbooks.io/leetcode-python/content/096%20Unique%20Binary%20Search%20Trees.html

首先明确n个不等的数它们能构成的二叉搜索树的种类都是相等的.

毫无头绪，对于1...n的bst，可以这样看，k可以作为root，那么1..k-1必定在左边，k+1...n必定在右边，而1...k-1课产生的bst树是dp[k-1],右边产生的数是dp[n-k],所以能生成的树的数量是 dp[k-1]* dp[n-k]

dp[n] = sum(dp[k-1]*dp[n-k])，从0到k

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [ 1 for i in range(n+1)]

        for i in range(2,n+1):
        	s = 0
        	for k in range(i):
        		s += dp[k]*dp[i-k-1]
        	dp[i] = s 

        return dp[-1]