链接：https://www.nowcoder.com/acm/contest/202/F
来源：牛客网
题目描述
平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。
给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。
输入描述:
两个整数，n, d.
输出描述:
一个整数：所有高度为 n 的平衡树中不平衡度的最大值。
示例1
输入
复制
4 1
输出
复制
5
说明
下面这棵树在 d=1 的定义下高度是平衡的，其不平衡度为 5。

备注:
0 ≤ n, d ≤ 60

这个也是坑爹，记忆化搜索出来明明和标准答案对拍过了，就是过了90%
算了，学习题解的方法，是用了类似递推或者说dp的思路，其实差不多，不过他的递推更加简洁
首先答案肯定是根节点的右子树满（完全二叉树），而右边是一颗最小平衡树
设f(h)为高度为h的最小平衡树节点
f ( h ) = h ( h &lt; = d ) 或 f ( h ) = f ( h − 1 ) + f ( h − d − 1 ) ( h &gt; d ) f(h)=h (h&lt;=d) 或 f(h)=f(h-1)+f(h-d-1) (h&gt;d) f(h)=h(h<=d)或f(h)=f(h−1)+f(h−d−1)(h>d)
第一种情况就是一条链的样子了，肯定满足小于d的平衡条件
第二种情况就是分成两棵子树的和了，一颗是h-1的高度，另一颗要尽可能小而且要满足平衡条件，然后还要加上自身的根节点

代码：

#include<cstdio>
using namespace std;
long long n,d,dp[130];
int main(){
   
    scanf("%lld%lld",&n,&d);
    for(int i=n-d-1;i>=1;i--)dp[i]=dp[i+1]+dp[i+d+1]+1;
    printf("%lld\n",(1ll<<(n-1))-1-dp[1]);
    return 0;
}