###### tags: `Leetcode` `medium` `dynamic programming` `python` `Top 100 Liked Questions`

# 96. Unique Binary Search Trees

## [題目連結:] https://leetcode.com/problems/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```.


#### [圖片來源:] https://leetcode.com/problems/unique-binary-search-trees/

## 解題想法:
* 題目為，給一數n，求出可由1~n構成的Binary Search Tree組合數
* 解法: 使用DP
* dp[i]: 由1~i可構成的BST個數
* 初始:
* dp[0]: 0個node-> 1種
* dp[1]: 1個node-> 1種
* 分別以2~n個node組成之BST
* 對於i個node組成之case:
* 對於i個node之中，每個node皆有當root之權利
* 數量分配: 每當計算i個數量時候
* root: 1 個node(自己)
* left: j 個nodes
* right: i-j-1個node
* 則此root=左子數之BST個數*右子數之BST之個數
* dp[i]+=dp[j] * dp[i-j-1]

## Python:

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        #dp[i]: 由1~i可構成的BST個數
        dp=[0]*(n+1)
        #init
        dp[0]=1
        dp[1]=1
        #dp 由2~n個node組成之BST
        for i in range(2,n+1):
            #個數分配:
            #root: 1 node
            #left: j nodes
            #right: i-j-1 nodes
            for j in range(i):
                dp[i]+=dp[j]*dp[i-j-1]
        return dp[n]

result = Solution()
ans = result.numTrees(n=3)
print(ans)