96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/#/description

这题是找BST有多少种可能的排列。
很多人提到，这题恰好用到了卡特兰数的那个sigma公式。

这个人的解释蛮清楚的：
The essential process is: to build a tree, we need to pick a root node, then we need to know how many possible left sub trees and right sub trees can be held under that node, finally multiply them.

取一个num做root，然后找出左子树和右子树分别有多少种可能的样子，然后相乘；最后相加。

至于为什么是multiply而不是add，是因为每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况。

这题的递推公式不止跟i-1有关系，可以写成:

dp[i] = sigma(dp[k] * dp(i-k-1)) , 0<=k<=i-1

To build a tree contains {1,2,3,4,5}. First we pick 1 as root, for the left sub tree, there are none; for the right sub tree, we need count how many possible trees are there constructed from {2,3,4,5}, apparently it's the same number as {1,2,3,4}. So the total number of trees under "1" picked as root is dp[0] * dp[4] = 14. (assume dp[0] =1). Similarly, root 2 has dp[1]dp[3] = 5 trees. root 3 has dp[2]dp[2] = 4, root 4 has dp[3]dp[1]= 5 and root 5 has dp[0]dp[4] = 14. Finally sum the up and it's done.

code:

    public int numTrees(int n) {
        int dp[] = new int[n + 1];
        //包含0个node的BST有1种
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++)
          //这里的j<i不要写成j<n了
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        return dp[n];
    }

ref:
http://www.cnblogs.com/springfor/p/3884009.html
http://fisherlei.blogspot.jp/2013/03/leetcode-unique-binary-search-trees.html