15. 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.

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

Approach

If we take a no of as root as its left subtree has 3 combinations and right subtree has 4 combinations total combinations for R = 3 * 4

If total no of nodes are 4 We can make each node as root once and count the combinations and add them.

Solution: (DP)

class Solution
{
public:
    int numTrees(int n)
    {

        vector<int> dp(n + 1);

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++)
        {

            for (int j = 1; j <= i; j++)
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
};