大家一起来数二叉树吧（牛客网动态规划+组合数学）

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

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

输入描述:
每一组输入一行，两个正整数n,m（n<=50）意义如题目
输出描述:
每一行输出一个数，表示相应询问的答案取模1000000007
示例1
输入
复制
4 2
10 5
输出
复制
6
252
备注:
a取模b等于a%b，即a除以b的余数
一开始以为是递推的题目，后来发现是动态规划。
可能对于动态规划真的不知道怎么想，一道2星的题目就要想很久。。
我们用dp[x][y]代表着x个结点有y个叶子节点的所有情况。
对于x个结点有y个叶子节点的这种情况，我们可以拿出一个结点来， 然后在左右枚举。再把结果累加到dp[x][y]上。
状态转移方程：dp[i][j]=(dp[i][j]+dp[i-x-1][j-y]*dp[x][y]%mod)%mod;
代码如下：

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;

const int maxx=51;
ll dp[maxx][maxx];
int n,m;

inline void init()
{
	dp[1][1]=1ll;
	dp[0][0]=1ll;
	for(int i=2;i<=50;i++)
	{
		for(int j=1;j<i;j++)
		{
			dp[i][j]=0;
			for(int x=0;x<i;x++)
			{
				for(int y=0;y<=x;y++)//y可以等于x，这就代表了选定的那个节点只有左子树或者只有右子树
				{
					if(y<=j) dp[i][j]=(dp[i][j]+dp[i-x-1][j-y]*dp[x][y]%mod)%mod;
					else break;
				}
			}
		}
	}
}
int main()
{
	init();
	while(~scanf("%d%d",&n,&m))
	{
		cout<<dp[n][m]<<endl;
	}
}

努力加油a啊，(^o)/~

最后

以上就是精明飞机为你收集整理的大家一起来数二叉树吧（牛客网动态规划+组合数学）的全部内容，希望文章能够帮你解决大家一起来数二叉树吧（牛客网动态规划+组合数学）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。