原题（Medium）：
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
我们或许可以先从数学的角度去思考这题，给定一个整数n，我们可以试着从根结点出发，此时根结点占去一个结点数，结点总数剩下n-1，那么剩下的结点数我们可以先考虑两种简单的情况，一是全部放左子树，二是全部放右子树，即（n-1, 0）和（0, n-1），如果我们知道整数n-1组成的二叉搜索树有多少种（假设x），那么我们就能知道整数n的二叉搜索树总数中有2x的那一部分；那么显然不止这两种情况，还有（n-2, 1）、（1, n-2）、（2, n-3）、（n-3, 2）.......的情况 ，我们似乎可以推导一条通式来涵盖所有情况：（i, n-i-1）、（n-i-1, i）（i从0开始，直到n-1），只要我们把各种情况的二叉搜索树种数累加，最后就能得到整数n的二叉搜索树种数。
例如：当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1; h(0)=0;
当n=2时，1个根节点固定，还有2-1个节点。这一个节点可以分成（1,0），（0,1）两组。即左边放1个，右边放0个；或者左边放0个，右边放1个。即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。
当n=3时，1个根节点固定，还有2个节点。这2个节点可以分成（2,0），（1,1），（0,2）3组。即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。（来自）
就此，我们代码的思路也就呼之欲出了。
思路：动态规划
DP就是这题的不二之选，虽然牺牲了点空间，但换来了速度上的提升。
1 int numTrees(int n) { 2 //特殊情况检查 3 if (n == 0 | n == 1) return n; 4 //建立一个DP数组，为了能获取到整数n的种数，把数组大小设为n+1 5 vector<int>DP(n + 1, 0); 6 //先初始化第0个和第1个元素 7 DP[0] = 1; 8 DP[1] = 1; 9 10 11 for (int i = 2; i <= n; i++) 12 { 13 for (int j = 0; j < i; j++) 14 DP[i] += (DP[j] * DP[i - j - 1]); 15 } 16 17 return DP[n]; 18 }