二叉树数目

发布时间 : 2025-12-29 16:59

小强现在有nn个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为nn且树的高度不超过m的方案.因为答案很大,所以答案需要模上1e9+7后输出.

树的高度: 定义为所有叶子到根路径上节点个数的最大值.

数据范围：1≤n,m≤50

记忆化搜索

#define int long long
int n,m;
int mod = 1e9+7;
int dp[51][51];
int f(int lv,int k) {
    if(k == 0) {
        return 1;
    }
    if(lv == 0) {
        return 0;
    }
    if(dp[lv][k] != -1) {
        return dp[lv][k];
    }
    int cnt = 0;
    for(int i = 0; i < k; i++) {
        cnt = (cnt + f(lv-1,k-1-i)*f(lv-1,i)%mod)%mod;
    }
    dp[lv][k] = cnt;
    return cnt;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            dp[i][j] = -1;
        }
    }
    cout<<f(m,n);
    return 0;
}

#define int long long
int n,m;
int mod = 1e9+7;
int dp[51][51];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 0; i <= n; i++) {
		dp[0][i] = 0;
	}
	for(int i = 0; i <= m; i++) {
		dp[i][0] = 1;
	}
	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= n; j++) {
			int cnt = 0;
			for(int k = 0; k < j; k++) {
				cnt = (cnt + dp[i-1][j-1-k]*dp[i-1][k]%mod)%mod;
			}
			dp[i][j] = cnt;
		}
	}
	cout<<dp[m][n];
    return 0;
}

滚动数组DP
注意更新顺序从后往前更新，否则会把上一轮的值覆盖

#define int long long
int n,m;
int mod = 1e9+7;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	cin >> n >> m;
	int dp2[n+1];
	dp2[0] = 1;
	for(int i = 1; i <= n; i++) dp2[i] = 0;
	for(int i = 1; i <= m; i++) {
		for(int j = n; j >= 1; j--) { 
			int cnt = 0;
			for(int k = j - 1; k >= 0; k--) {
				cnt = (cnt + dp2[j-1-k]*dp2[k]%mod)%mod;
			}	
			dp2[j] = cnt;
		}
	}
	cout<<dp2[n];
    return 0;
}