96. Unique Binary Search Trees

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

This is a dp question. count of 3 =

  * if 1 is root, then count[0] * count[2];
  * if 2 is root, then count[1] * count[1];
  * if 3 is root, then count[2] * count[0];

from above deduction, so empty subtree is one, if take one node as root, number smaller than root will form left sub tree. and others to form right sub tree.

public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] =1;
        dp[1]=1;
        for(int i=2; i<= n; i++){
            for(int j=1; j<=i;j++) // take j as root, j-1 nodes form left subtree, i-j nodes forms right subtree.
                dp[i] += dp[j-1] * dp[i-j];
        }
        return dp[n];
    }
}