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.

&nbsp;
Example 1:

Input: n = 3
Output: 5


Example 2:

Input: n = 1
Output: 1


&nbsp;
Constraints:


	1 &lt;= n &lt;= 19


class Solution(object):
    def numTrees(self, n):
        if n == 0 or n == 1:
            return 1
        # Create 'sol' array of length n+1...
        sol = [0] * (n+1)
        # The value of the first index will be 1.
        sol[0] = 1
        # Run a loop from 1 to n+1...
        for i in range(1, n+1):
            # Within the above loop, run a nested loop from 0 to i...
            for j in range(i):
                # Update the i-th position of the array by adding the multiplication of the respective index...
                sol[i] += sol[j] * sol[i-j-1]
        # Return the value of the nth index of the array to get the solution...
        return sol[n]
class Solution {
    public int numTrees(int n) {
        // Create 'sol' array of length n+1...
        int[] sol = new int[n+1];
        // The value of the first index will be 1.
        sol[0] = 1;
        // Run a loop from 1 to n+1...
        for(int i = 1; i <= n; i++) {
            // Within the above loop, run a nested loop from 0 to i...
            for(int j = 0; j < i; j++) {
                // Update the i-th position of the array by adding the multiplication of the respective index...
                sol[i] += sol[j] * sol[i-j-1];
            }
        }
        // Return the value of the nth index of the array to get the solution...
        return sol[n];
    }
}
class Solution {
public:
    
    int catalan (int n,vector<int> &dp)
    {
        if(n<=1)
            return 1;
        
        int ans =0;
        for(int i=0;i<n;i++)
        {
            ans+=catalan(i,dp)*catalan(n-1-i,dp);
        }
        
        return ans;
    }
    int numTrees(int n) {
        
        vector<int> dp(n+1,-1);
        
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i=2;i<=n;i++)
        {
            int ans = 0;
            for(int j=0;j<i;j++)
            {
                ans += dp[j]*dp[i-1-j];
            }
            dp[i] = ans;
        }
        
        return dp[n];
        
        // return catalan(n,dp);
        
    }
};
var numTrees = function(n) {
    // Create 'sol' array to store the solution...
    var sol = [1, 1];
    // Run a loop from 2 to n...
    for (let i = 2; i <= n; i++) {
        sol[i] = 0;
        // Within the above loop, run a nested loop from 1 to i...
        for (let j = 1; j <= i; j++) {
            // Update the i-th position of the array by adding the multiplication of the respective index...
            sol[i] += sol[i - j] * sol[j - 1];
        }
    }
    // Return the value of the nth index of the array to get the solution...
    return sol[n];
};
Unique Binary Search Trees