Leetcode: Unique Binary Search Trees

Unique Binary Search Trees

My Submissions

Total Accepted: 68487 Total Submissions: 189330 Difficulty: Medium

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Subscribe to see which companies asked this question

Hide Tags

 Tree Dynamic Programming

Show Similar Problems

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP: 

1. binary search tree: small in left and large in right

2. see the rules below:

so, the rule for c(n) =c(0)*c(n-1)+c(1)*c(n-2)+ ... +c(n-1)*c(0)

//////////////////////////////////////////////////////////////////////////////////

//codes

class Solution {

public:

    int numTrees(int n) {

        vector<int> dp;

        dp.assign(n+1,0);

        dp[0]=1;

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

            for (int j=0;j<i;j++){

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

            }

        }

        return dp[n];

    }

};