长沙理工大学第十二届ACM大赛 K 大家一起来数二叉树吧（动态规划）

77 阅读 0 评论 51 点赞

我是靠谱客的博主外向大雁，最近开发中收集的这篇文章主要介绍长沙理工大学第十二届ACM大赛 K 大家一起来数二叉树吧（动态规划），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

某一天，Zzq正在上数据结构课。老师在讲台上面讲着二叉树，zzq在下面发着呆。

突然zzq想到一个问题：对于一个n个节点，m个叶子的二叉树，有多少种形态呐？你能告诉他吗？

对于第一组样例的解释

输入描述:

每一组输入一行，两个正整数n,m（n<=50）意义如题目

输出描述:

每一行输出一个数，表示相应询问的答案取模1000000007

示例1

输入

4 2
10 5

输出

6
252

备注:

杭电曾经做过一个给出树的高度和叶子点个数让求有多少种组合方式。。

脑子笨没有想过这道题差不多。。

从底层网上加。

先跑层数为1的。。

每个情况 n个节点 m的叶子节点

都可以由 i个子节点 j个叶子节点的树的种类数 * （n - i -1）个子节点 m-j个叶子节点树的种类数也就是在两颗子树的根节点再添加一个节点。

图丑莫怪就是这个意思。

#include<stdio.h>
#include<string.h>
using namespace std;
#define N 55
#define Mod 1000000007
#define ll long long
ll dp[N][N];

int main()
{
    ll n,m;
    memset(dp,0,sizeof(dp));
    dp[0][0]=dp[1][1]=1;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=i; j++)
        {
            for(int ii=0;ii<i;ii++)
            {
                for(int jj=0;jj<=j;jj++)
                {
                    dp[i][j]+=dp[i-ii-1][j-jj]*dp[ii][jj];
                    dp[i][j]%=Mod;
                }
            }
        }
    }

    while(~scanf("%lld%lld",&n,&m))
    {
        if(n<m)
            printf("0n");
        else
        printf("%lldn",dp[n][m]);
    }
}