Posted on 2014-01-12 01:16
Uriel 閱讀(141)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
LeetCode
求n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)為1~n的BST有多少種
水題吧算是，對(duì)于n個(gè)節(jié)點(diǎn)的BST，1~n都有可能是其樹根，于是1~n輪流做根，假設(shè)此時(shí)樹根為i，則以i為根的n個(gè)節(jié)點(diǎn)的BST數(shù)目為i-1個(gè)節(jié)點(diǎn)的BST數(shù)目乘以n-i個(gè)節(jié)點(diǎn)的BST數(shù)目
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 };