96. Unique Binary Search Trees

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

 

Constraints:

• 1 <= n <= 19

The solution in C++ using DP

           3                          2                         1               
          / \                        / \                      /   \      
numTrees(2) numTrees(0)    numTrees(1) numTrees(1)   numTrees(0) numTrees(2)              
         i = 3                      i = 2                     i = 1           
		 
                      i
	=>              /   \ 
         numTrees(i-1)	numTrees(n-i)

class Solution {

public:

    int dp[20];

    int numTrees(int n) {

         dp[0]=1;

        dp[1]=1;

        if(n <= 1){

            return dp[n];

        }

       

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

            if(dp[i-1]==0) dp[i-1]=numTrees(i-1);

            if(dp[n-1]==0) dp[n-i]=numTrees(n-i);

            dp[n] += dp[i-1]* dp[n-i];

        }

           

        return dp[n];

    }

};