UniqueBinarySearchTrees.java

package dynamic_programming;

/**
 * Created by gouthamvidyapradhan on 31/03/2017. Given n, how many structurally unique BST's (binary
 * search trees) that store values 1...n?
 *
 * <p>For example, Given n = 3, there are a total of 5 unique BST's.
 *
 * <p>1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
 */
public class UniqueBinarySearchTrees {
  int[] dp;

  /**
   * Main method
   *
   * @param args
   */
  public static void main(String[] args) throws Exception {
    System.out.println(new UniqueBinarySearchTrees().numTrees(5));
  }

  public int numTrees(int n) {
    dp = new int[n + 1];
    dp[0] = 1;
    return dp(n);
  }

  private int dp(int n) {
    if (dp[n] != 0) return dp[n];
    for (int i = 1; i <= n; i++) {
      dp[n] += dp(n - i) * dp(n - (n - i) - 1);
    }
    return dp[n];
  }
}