<jupyter_start><jupyter_text>Given n, how many structurally unique BST's (binary search trees) that store values 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       **Catalan number:$$C_{0}=1 \text { and } C_{n+1}=\sum_{i=0}^{n} C_{i} C_{n-i} \text { for } n \geq 0$$<jupyter_code># The number of such BST is called Catalan number
def numTrees(n):
    if n <=1 : 
        return 1 
    res = 0 
    for i in range(n): 
        res += numTrees(i) * numTrees(n-i-1) 

    return res 
numTrees(3)<jupyter_output><empty_output><jupyter_text>**This solution exceeds time limits, now try dynamic programmingFor all possible values of i, consider i as root, then `[1….i-1]` numbers will fall in the left subtree and `[i+1….n]` numbers will fall in the right subtree. So, add `(i-1)*(n-i)` to the answer. The summation of the products will be the answer to the number of unique BST.<jupyter_code>def numTrees(n):
    dp = [0]*(n+1) # each element represents number of BST using elements with values of 1,2,3,...,i
    dp[0]=1
    dp[1]=1
    for i in range(2,n+1):
        for j in range(1,i+1):
            dp[i]=dp[i]+dp[i-j]*dp[j-1] #apply the method described above, make sure j-1 starts from 0
            
    return dp[n]
numTrees(3)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12113232389730086, 'fraction_numerical': 0.03357472021066491, 'mean_word_length': 2.0522088353413657, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '175562', 'license': 'MIT', 'n_tokens_mistral': 547, 'n_tokens_neox': 515, 'n_words': 182, 'path': 'Unique_Binary_Search_Trees.ipynb', 'repo_name': 'Lonitch/hackerRank', 'size': '1519'}