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;
}