LEET code -- Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

這題要去把圖畫出來才明顯

我們只要管root在哪裡   在看他左右個剩下幾個點   就可以知道它下面可以怎麼變化

number of BSTs with k being the root 
= count of BSTs of k-1 consecutive numbers * count of BSTs of n-k consecutive numbers

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

int numTrees(int n) { //tree[0]=with 0 tree has only 1 bts //tree[1]=with 1 tree node and have 1 bts //tree[2]=with 2 node, and 2 bts //tree[3]=with 3 ndoe, has 5 bts /* v 1 2 3 4 5-->2~5 is the tree[4] V 1 2 3 4 5-->1 is three[1],3~5 is tree[3] V 1 2 3 4 5-->1~2 is tree[2],4~5 is tree[2] therefore, we can cacaluate the result */ int tree[n+1]; tree[0]=1; tree[1]=1; for(int i=2;i<=n;i++){ int sum=0; for(int j=1;j<=i;j++){ sum+=tree[j-1]*tree[i-j]; } tree[i]=sum; } return tree[n]; }