96 不同的搜索树
这道题正常人应该很难想到。。。
dp[i]表示节点1到节点i的搜索树个数
递推公式
\(dp[i] = \sum_{1}^{i}j为头节点的搜索树个数\)
j为头节点搜索树个数计算方法:dp[j - 1] * dp[i - j]
class Solution {
public:
int numTrees(int n) {
// dp[i]表示节点1到节点i的搜索树个数
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1;i <= n; i++){
// 枚举头节点, j为头节点的值
// 根据搜索树特性,j - 1为左子树的个数, i - j为右子树的个数
for(int j = 1; j <= i; j++){
// 递推公式
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};