96. Unique Binary Search Trees

// for each n, we could let the root be any number in the range [1, n]
// after determining the root, the nodes of left subtree and the right subtree are also determined
// but subtree also have lots of style, so we need to multiple the left subtree's possible styles and the right subtree's possible styles 
// this question is the definition of Catalan number
// we could get the result just using math

class Solution 
{
public:
    // int numTrees(int n) 
    int numTrees(const int i_nodeCount) 
    {
        long long int result = 1;
        for(int i = 0; i < i_nodeCount; i++)
        {
            result = result * 2*(2*i+1) / (i+2); 
        }
        
        return result;
    }
};

// also, we could solve the question by dynamic programming

class Solution 
{
public:
    // int numTrees(int n) 
    int numTrees(int n) 
    {
        vector<int> possibleStyleCount(n + 1); // add 0 node to simplify the calculation
        possibleStyleCount[0] = possibleStyleCount[1] = 1;
        
        for(int i = 2; i <= n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                possibleStyleCount[i] += possibleStyleCount[j] * possibleStyleCount[i - j - 1];

                // nodes count = left subtree's node + root + right subtree's node
                // so if the right subtree has j nodes, right subtree has i-j-1 nodes
            }
        }
        
        return possibleStyleCount[n];
    }
};