Leetcode 96. Unique Binary Search Trees (Python)

Related Topic

Dynamic-Programming.

Description

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

Sample I/O

Example 1

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

Methodology

Unlike most people use list as cache, I use dictionary here. The performance for add and get will be exactly same. It is only good for when you want to print the DP result.

So DP dictionary has key, value pair. The key represent the number of left side children or the number of right side children and the value represnt the number of possible subtree. The answer is sum of each root’s posibilities of substree

For example:

n = 1, the root is 1

there is 0 left childen or 0 right children, root is the only node dp[0] = 1 represnt there is 1 possible substree for the root has 0 left children or 0 right children. Here 1 possible subtree is node(None)

so when n = 1, ans is dp[0]xdp[0] = 1

	1

n = 2, the root is either 1 or 2

when root is 1 there is 0 left children and 1 right children when root is 2 there is 1 left children and 0 right children dp[1]=1 represent there is 1 possible substree for the root has 1 left children or 1 right children. Here the 1 possible substree is left child node(1) when 2 is the root and right child node(2) when 1 is the root.

so when n =2, the ans is dp[1]xdp[0]+dp[0]xdp[1] = 2

	   2                   1 
	  /          or          \
	 1                        2

n = 3, the root is 1,2 or 3

when root is 1 there is 0 left children and 2 right children when root is 2 there is 1 left children and 1 right children when root is 3 there is 2 left children and 0 right children dp[2] = 2 represent there is 2 possible substree for the root has 2 left children or 2 right children.

and based on the above pattern we know that when root has 1 left children or 1 right children, here the 2 possible substree is left children node(1or 2) when root is 3 or right children node (2,3) when root is 1.

so when n = 3, the ans is dp[0]xdp[2] + dp[2]xdp[0] + dp[2]xdp[0] + dp[1]xdp[1] + dp[0]xdp[1]=5

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

Code

def numTrees(self, n: int) -> int:
        dp = {0:1, 1:1, 2:2}
        if n < 3: return dp[n]
        for i in range(3, n+1):
            num = 0
            for j in range(i):
                num += dp[j]*dp[i-j-1]
            dp[i] = num
        return dp[n]

BigO

We iterate all input list, it will cost O(n-2), each value will add up previous value as result, it will cost ((n-2)n/2) It is O(n^2)