题目
给你一个整数n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
?
题解
思路：dp时间到！注意到二叉搜索树的性质使得当[1, n]中的某一个数m为根的时候，根的两侧分别为[1, m - 1]，[m + 1, n]。两侧都是连续的数字，且数量小于n，满足dp性质。所以从n = 0, 1的时候开始构建。对每一棵结点数固定的二叉搜索树，分别考虑[1, n]中每一个数为根的情况进行累加。
int numTrees(int n) {
int num[n + 1];
num[0] = 1;
num[1] = 1;
int sum;
for(int i = 2; i <= n; i++){ // 搜索树结点数为i
sum = 0;
for(int j = 0; j < i; j++){ // 根结点为j的情况
sum += num[j] * num[i - 1 - j];
}
num[i] = sum;
}
return num[n];
}
用vector初始化为0可以避免使用变量sum，但跑出来用vector占用的空间反而更大，最后还是选用了数组的方法。
