leetcode 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
采用dp[i] 表示含有i个节点的二叉搜索树，其中二叉搜索树由左子树和右子树以及根结点组成。其中dp[i]由含有i-j节点的左子树和j-1节点的右子树和一个根结点组成。所以dp[i]的构造形式由左右子树决定。
最优子结构 dp[i]
状态转移方程：dp[i] += (dp[i - j] * dp[j - 1])
int numTrees(int n) {
int dp[20] = {0};
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
dp[i] += (dp[i - j] * dp[j - 1]);
}
}
return dp[n];
}