leetCode Leetcode基础刷题之PHP解析(96. Unique Binary Search Trees)
.
✏题目描述
给定一个整数n，求从1到n有多少组二叉查找树组合。
✏题目实例
✏题目分析
好吧，这道题其实是一个卡塔兰数例子。。。只听过斐波拉契数。。特意从维基百科截了一张图你们感受一下。
**求最终有多少种情况，其实本质上就是左子树的情况加右子树的情况。如果n等于0，值等于1。因为空树也是二叉查找树。n等于1，1就是根节点，左右子树都为空，所以结果也是1.
如果n等于2的话，1，2都能作为树的根节点,如果1为根节点，那么左子树就是空，右子树就是2**
dp[2]=dp[0]*dp[1]+dp[1]*dp[0]=2
如果n=3，1,为根节点的话，左子树没节点。右子树两个结点，2为根结点的话，左右子树各一个结点，3为根节点的话和1是根节点相反的情况。
dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]
✏代码实现
/**
* @param Integer $n
* @return Integer
*/
function numTrees($n) {
$dp[0]=$dp[1]=1;
for($i=2;$i<=$n;$i++){
for($j=0;$j<$i;$j++){
$dp[$i]+=$dp[$j]*$dp[$i-$j-1];
}
}
return $dp[$n];
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)