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

這題是找BST有多少種可能的排列。
很多人提到，這題恰好用到了卡特蘭數(shù)的那個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，是因為每個左邊的子樹跟所有右邊的子樹匹配，而每個右邊的子樹也要跟所有的左邊子樹匹配，總共有左右子樹數(shù)量的乘積種情況。

這題的遞推公式不止跟i-1有關(guān)系，可以寫成:

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