每日一题：高度不超过m的二叉树个数

题目

求 $n$ 个节点，高度不超过 $h$ 的二叉树的个数，结果模 $1e9 + 7$。

Solution

定义 $f[i][j]$ 为 $i$ 个点组成高度不超过 $j$ 的二叉树的数量，则得到状态转移方程：$f[i][j] = f[k][j-1] * f[i-k-1][j-1]$，表示即选出一个根节点，两边子树高度不超过 $j - 1$ 的数量，初始状态为 $f[0][i] = 1$。

Code

#include <cstdio>
typedef long long ll;
const ll mod = 1e9 + 7;
int n, h;
ll f[100][100];

int main() {
  scanf("%d%d", &n, &h);
  for (int i = 0; i <= n; i++) f[0][i] = 1;
  for (int j = 1; j <= n; j++)
    for (int i = 1; i <= n; i++)
      for (int k = 0; k < i; k++)
        f[i][j] = (f[i][j] + f[k][j - 1] * f[i - k - 1][j - 1]) % mod;
  printf("%lld", f[n][h]);
  return 0;
}