1.题目
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.
13321\/// \\3211 32//\\ 2123
2.解决方案
class Solution {public:int numTrees(int n) {vector<int> num;num.push_back(1);for(int i=1; i<=n; i++){num.push_back(0);if(i<3)num[i]=i;else{for(int j=1; j<=i; j++)num[i]+=num[j-1]*num[i-j];}}return num[n];}}; 思路：
我们先从0开始分析
0 当没有一个二分搜索树没有任何节点也是一种情况，即Tree[0] = 1
1 当一个二分搜索树只有一个节点也是一种情况，即Tree[1] = 1
2 当一个二分搜索树有2个节点时,肯定要有一个节点作为根节点，，那样总的数量就是，Tree[2] = Tree[0] * Tree[1] + Tree[1] * [0]
3 当一个二分搜索树有3个节点时,肯定要有一个节点作为根节点，那样总的数量就是，Tree[3] = Tree[0] * Tree[2] + Tree[1] * [1] + Tree[2] * [0]
这里用了动态规划的思想，把之前已经算过的保存在数组中。
第一个青春是上帝给的;第二个的青春是靠自己努力的
