资讯 安全 论坛 下载 读书 程序开发 数据库 系统 网络 电子书 微信学院 站长学院 QQ 考试
频道栏目
其他| 安全资讯| 安全公告| 病毒预警| 人物| 企业招聘| 其他综合|
登录注册
首页 > 资讯 > 其他 > 正文

D.How many trees?（dp）节点问题求解

17-12-23        来源：[db:作者]  
收藏   我要投稿

Description

求n个节点构成的高度不小于h的二叉树数量

Input

两个整数n,h(1≤h≤n≤35)

Output

输出n个节点构成的高度不小于h的二叉树数量

Sample Input

3 2

Sample Output

5

Solution

dp[n][h]表示n个节点构成的高度为h的二叉树数量，枚举左儿子节点数量x和高度h1以及右儿子高度h2，则右儿子节点数量为n?1?x，进而有转移方程dp[n][h]=∑h1,h2,xdp[x][h1]?dp[n?1?x][h2]，记忆化一下即可

Code

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pairP;
const int maxn=40;
bool flag[maxn][maxn];
ull dp[maxn][maxn];
ull Solve(int n,int h)
{
    if(flag[n][h])return dp[n][h];
    flag[n][h]=1;
    if(n==h)
    {
        if(n==0)return dp[n][h]=1;
        return dp[n][h]=1ull<<(n-1);
    }
    if(((1ll<<><>
        
   
<>
点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇：C.Digital Root（数论）求解
下一篇：vue学习（一）：环境搭建
相关文章
热门专题推荐 vmware win7激活工具 win10激活工具 excel word office激活 小马激活工具 重装系统 数据恢复 u盘启动工具
图文推荐
文章
推荐
热门新闻
· 锤子坚果Pro发布后，罗永浩哭了
· 想实习的大学党看过来!这些科技巨头最
· 罗永浩锤子发布会抢先消息：锤子科技新
· Google新一代系统Fuchsia OS界面曝光
· 中国唯一连续运营20余年的网络游戏，还
· iPhone都便宜了 为何国产手机越来越贵
· 丢人！谷歌和Facebook竟被虚假企业电邮
· 中国移动支付震惊日本网友 为什么美国

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站