---
# System prepended metadata

title: 96. Unique Binary Search Trees
tags: [Leetcode, medium, python, Top 100 Liked Questions, dynamic programming]

---

###### 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://i.imgur.com/9I6iI7i.png)

#### [圖片來源:] 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:
``` 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)
```