class Solution {
//根为i的二叉搜索树的数量=左子树二叉搜索树的数量乘以右子树二叉搜索树的数量
//dp[i]表示i个节点时二叉搜索树的数量
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
![[CTFshow 红包挑战] 刷题记录](https://img-blog.csdnimg.cn/direct/5874d5c1942a46468543504f622e609b.png)
