NC19775 平衡二叉树(记忆化搜索 || dp)

题目链接

题意：
$建一棵高度为n，并且每个结点的左右子树高度差不超过d的平衡二叉树$
$在这基础上，问这个平衡树的左右子树的结点个数差最多为多少$
题解：
$n,d<=60$
$想要结点个数差最大，肯定是一棵子树结点个数最少，另外一个最大$
$并且要让最大的子树的高度比另一棵多d$
$最大直接造一棵高度为n的满二叉树，2^{n-1}-1$
$另一棵肯定尽量造一个结点比较少的平衡二叉树$

$考虑造结点少的平衡二叉树，高度首先为n-d-1$
$假设当前树高为h，想要恰好满足题目要求并且最少$
$那就是建一棵高度为h-1的子树，和一棵h-d-1的子树$
$可以通过记忆化搜索进行计算$
$边界条件$
$1.h<=0的时候返回0$
$2.h==1的时候返回1$
$其余的返回建左树+建右树+1的个数即可$

$也可以用dp计算，思想类似$
$dp[i]表示高度为i时恰好建成一个题目要求的平衡二叉树的结点个数$
$转移方程为dp[i]=dp[i-1]+dp[i-d-1]+1$
$就是建一棵高度i-1的子树和i-d-1的子树并加根$

$最后用最大的减后来计算的高度为n-d-1的个数$

AC代码
~~初学python，上一手拙劣代码~~

n, d = map(int,input().split())
f=[0 for i in range(140)]
f[1]=1
for i in range(2, n+1):
    f[i] = 1 + f[i - 1] + f[i - d - 1]
print((1 << n - 1) - 1 - f[n - d - 1])