LeeCode - 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

思路：

找規律

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));
    }

}