https://leetcode.com/problems/unique-binary-search-trees/#/description
這題是找BST有多少種可能的排列虫碉。
很多人提到算行，這題恰好用到了卡特蘭數(shù)的那個(gè)sigma公式旨怠。
這個(gè)人的解釋蠻清楚的：
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.
取一個(gè)num做root捂掰，然后找出左子樹(shù)和右子樹(shù)分別有多少種可能的樣子贝椿，然后相乘想括；最后相加。
至于為什么是multiply而不是add烙博，是因?yàn)?strong>每個(gè)左邊的子樹(shù)跟所有右邊的子樹(shù)匹配瑟蜈，而每個(gè)右邊的子樹(shù)也要跟所有的左邊子樹(shù)匹配烟逊，總共有左右子樹(shù)數(shù)量的乘積種情況。
這題的遞推公式不止跟i-1有關(guān)系铺根，可以寫(xiě)成:
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個(gè)node的BST有1種
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++)
//這里的j<i不要寫(xiě)成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
