不同的二叉搜索树
题目
思路
DP：根的左右子树情况数相乘，卡特兰数：递推式:h(n)=h(n-1)(4n-2)/(n+1);
代码
DP
class Solution {
public:
int numTrees(int n
) {
vector
<int> dp(n
+1,0);
dp
[0]=dp
[1]=1;
for(int i
=2;i
<=n
;i
++)
for(int j
=0;j
<i
;j
++)
dp
[i
]+=dp
[j
]*dp
[i
-j
-1];
return dp
[n
];
}
};
卡特兰数
class Solution {
public:
int numTrees(long long n
) {
if(n
==1) return 1;
return numTrees(n
-1)*(4*n
-2)/(n
+1);
}
};
