Posted on 2014-01-12 01:16
Uriel 閱讀(128)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
求n個節(jié)點，節(jié)點編號為1~n的BST有多少種
水題吧算是，對于n個節(jié)點的BST，1~n都有可能是其樹根，于是1~n輪流做根，假設此時樹根為i，則以i為根的n個節(jié)點的BST數目為i-1個節(jié)點的BST數目乘以n-i個節(jié)點的BST數目
1 class Solution {
2 public:
3 int dp[100010];
4 int numTrees(int n) {
5 dp[0] = dp[1] = 1;
6 for(int i = 2; i <= n; ++i) {
7 dp[i] = 0;
8 for(int j = 1; j <= i; ++j) {
9 dp[i] += dp[j - 1] * dp[i - j];
10 }
11 }
12 return dp[n];
13 }
14 };