Number of Unique BST with a given key | Dynamic Programming | C ++ code to find number of unique BSTs Dynamic Programming solution ; Function to find number of unique BST ; DP to store the number of unique BST with key i ; Base case ; fill the dp table in top - down approach . ; n - i in right * i - 1 in left ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int numberOfBST ( int n ) { int dp [ n + 1 ] ; fill_n ( dp , n + 1 , 0 ) ; dp [ 0 ] = 1 ; dp [ 1 ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= i ; j ++ ) { dp [ i ] = dp [ i ] + ( dp [ i - j ] * dp [ j - 1 ] ) ; } } return dp [ n ] ; } int main ( ) { int n = 3 ; cout << " Number ▁ of ▁ structurally ▁ Unique ▁ BST ▁ with ▁ " << n << " ▁ keys ▁ are ▁ : ▁ " << numberOfBST ( n ) << " STRNEWLINE " ; return 0 ; }