LeetCode96.不同的二叉搜索树
题目来源:https://leetcode-cn.com/problems/unique-binary-search-trees/description/
题目描述:
就跟斐波那契数列一样,我们把n = 0 时赋为1,因为空树也算一种二叉搜索树,那么n = 1时的情况可以看做是其左子树个数乘以右子树的个数,左右字数都是空树,所以1乘1还是1。那么n = 2时,由于1和2都可以为跟,分别算出来,再把它们加起来即可。n = 2的情况可由下面式子算出:
num[2] = num[0] * num[1](1为根的情况) + num[1] * dp[0](2为根的情况)
同理可写出 n = 3 的计算方法:
num[3] = num[0] * num[2] (1为根的情况) + num[1] * num[1] (2为根的情况) + num[2] * num[0] (3为根的情况)
由此可以得出卡塔兰数列的递推式为:
根据以上分析,该题代码如下:
int numTrees(int n) {
int num[n+1];
num[0]=1;
num[1]=1;
for(int i=2;i<=n;i++){
num[i]=0;
for(int j=1;j<=i;j++){
num[i]=num[i]+num[i-j]*num[j-1];
}
}
return num[n];
}