Posted on 2014-01-12 01:16
Uriel 阅读(112)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
求n个节点，节点编号为1~n的BST有多少种
水题吧算是，对于n个节点的BST，1~n都有可能是其树根，于是1~n轮流做根，假设此时树根为i，则以i为根的n个节点的BST数目为i-1个节点的BST数目乘以n-i个节点的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 };