leetcode 96.不同的二叉搜索树
1.题目要求：
2.题目代码:
class Solution {
public:
int numTrees(int n) {
//创建dp数组
//了解dp的下标含义
//递推公式
//初始化
//确定遍历顺序
//打印dp数组
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
//设置dp数组
vector<int> dp;
//给dp数组设置空间的大小
dp.resize(n + 1,0);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i <= n;i++){
int j = 1;
while(j <= i){
dp[i] += (dp[j - 1] * dp[i - j]);
j++;
}
}
return dp[n];
}
};