140. 好二叉树(卡码网周赛第二十四期(23年腾讯音乐笔试真题))
题目描述
小红定义一个二叉树为“好二叉树”,当且仅当该二叉树所有节点的孩子数量为偶数(0 或者 2)。 小红想知道,n(1<= n <=3000)个节点组成的好二叉树,共有多少种不同的形态?
答案请对 10 ^ 9 + 7 取模。
输入
输入一个正整数 n
输出
输出一个正整数,代表好二叉树的数量
样例1输入
5
样例1输出
2
样例1输入
55
样例1输出
550429273
题解1(C++版本)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3010;
const LL MOD = 1e9 + 7;
int n;
LL dp[N];
LL dfs(int x){
if(x%2 == 0) return 0;
if(x == 1) return 1;
if(dp[x] != -1) return dp[x];
LL sum = 0;
for(int i = 1; i < x; i++){ // 总共x个节点,左子树为i个节点,右子树为x-1-i个节点的好二叉树的不同形态数
sum = (sum + dfs(i) * dfs(x - 1 - i)) % MOD;
}
return dp[x] = sum;
}
int main(){
scanf("%d", &n);
if(n%2 == 0) {
printf("0\n"); // n为偶数
return 0;
}
memset(dp, -1, sizeof dp);
printf("%lld\n", dfs(n));
return 0;
}