题目：

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

思路：

找规律

1. 没有节点，BST （Binary Search Tree）为1个， 即空树

2. 有一个节点，BST为1个，即自身为根节点

3. 有二个节点，BST为2个，1为root，左为空，右为2；2为root，左为1，右为空，其实就是dp[0]*dp[1] + dp[1]*dp[0]

      1                  2

        \               /

         2            1

4. 有三个节点

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

可以推出dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

package bst;public class UniqueBinarySearchTrees {    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 = 0; j < i; ++j) {                dp[i] += dp[j] * dp[i - 1 - j];            }        }        return dp[n];    }        public static void main(String[] args) {        // TODO Auto-generated method stub        UniqueBinarySearchTrees u = new UniqueBinarySearchTrees();        System.out.println(u.numTrees(3));    }}