题目:
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
class Solution {
public:
int numTrees(int n)
{
// 1、确定dp数组的下标及其含义
// 2、找出递推关系 dp[i] = dp[i] + dp[j - 1]*dp[i-j]
// dp[j-1]是以 j-1 为头结点左子树节点数量, dp[i-j]是以j为头结点右子树节点数量
// 后面两项的和 是 n-1 ,因为除去了一个根节点嘛~~~
// 3、dp数组的初始化
// 4、确定遍历顺序
// 这道题的递推·公式比较难想呀~
/*
错误一:dp 数组大小为 n+1 ,那么它的最后一个元素就是 dp[n] 嘛!
错误二:for循环的起始下标是 dp数组初始化后 接下来的那个下标,这个不要写错啦
错误三:内层 for 循环的终止条件是 j <= i
*/
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
// 这里必须是 += 否则就不是你想要的结果
dp[i] = dp[i] + dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};