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