大家一起来数二叉树吧

题号：NC13593 链接：https://ac.nowcoder.com/acm/problem/13593 来源：牛客网

题目描述 某一天，Zzq正在上数据结构课。老师在讲台上面讲着二叉树，zzq在下面发着呆。 突然zzq想到一个问题：对于一个n个节点，m个叶子的二叉树，有多少种形态呐？你能告诉他吗？ 对于第一组样例的解释

思路: 这是典型的动态规划，状态变量：n个节点，m个叶子决定了数量。

即dp[n][m]代表n个节点，m个叶子的数量

因为是二叉树，要么是左边，要么是右边，也就是说，n个节点除了给根节点外，还是剩下n-1个，这个n-1个节点要么在左边，要么在右边。叶子也是一样，要么在左边，要么在右边。

因此：

dp[n][m] = ∑(dp[k1][k2]*dp[n-1-k1][m-k2]), 其中k1，k2范围为[0,n-1],[0,m]

dp[k1][k2]如果k2>k1,显然这个值为0

附代码:

```// dddd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int main() {
	int n,m;
	long long dp[100][100];
	n = 50;
	for (int i = 0; i <= n; i++) {
		dp[0][i] = 0;
		dp[1][i] = 0;
	}
	dp[0][0] = 1;
	dp[1][1] = 1;
	
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			dp[i][j] = 0;
			for (int k1 = 0; k1 <= i-1; k1++) {
				for (int k2 = 0; k2 <= j; k2++) {
					dp[i][j] += dp[k1][k2] * dp[i - 1 - k1][j - k2];
					dp[i][j] %= 1000000007;
				}
			}
		}
		for (int j = i + 1; j <= n; j++) {
			dp[i][j] = 0;
		}
	}
	while (scanf("%d%d", &n, &m) > 0) {
		cout << dp[n][m] << endl;
	}
	return 0;
}