LeetCode 不同的二叉搜索树(动态规划)
解题思路:以i为根,左边为[1,i-1],共i-1个数,右边为[i+1,n]共n-i-1个数。
因此要计算以i为根的搜索二叉树的个数,就应当计算左子树和右子树二叉搜索树的个数相乘。这样一步步迭代,就可以归纳出等式。
dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2]+…+dp[n-2]*dp[1]+dp[n-1]*dp[0];
这里n代表数的个数,即连续的n个整数组成的二叉搜索树的种类。
这里我写的代码比较繁琐,看了别人的代码后,觉得很收益,记录下来,提醒自己要写简介的代码。
我的实现:
这里为了减少计算的次数,我将i进行了分类,分别为奇数和偶数。
public int numTrees(int n) {
int dp[] = new int[n+1];
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++)
{
int k = 0;
if(i%2==1){
while(k<=i/2-1){
dp[i] += dp[k]*dp[i-k-1];
k++;
}
dp[i] *= 2;
dp[i] += dp[i/2]*dp[i/2];
}else{
while(k<=(i-1)/2){
dp[i] += dp[k]*dp[i-k-1];
k++;
}
dp[i] *= 2;
}
}
return dp[n];
}
其实不用分类写,代码更简洁。
public int numTrees(int n) {
int dp[] = new int[n+1];
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++)
{
int k = 0;
while(k<=i-1){
dp[i] += dp[k]*dp[i-k-1];
k++;
}
}
return dp[n];
}