2023-06-01
题目
难度&重要性(1~10):5
题目来源
Codeforces,luogu
题目算法
dp
解题思路
深度最大为 \(n\left(1\le n\le 35\right)\) 的二叉树暴力枚举显然不行，考虑dp。
设 \(f_{i,j}\) 表示有 \(i\) 个节点时，深度不大于 \(j\) 的二叉树数量。
答案容斥：\(f_{n,n}-f_{n,h-1}\)。
这里，我们可以枚举 \(i-1\) 的左右儿子数量的状况来转移:
注意，这里我们要先枚举 \(j\)，再枚举 \(i\),以保证前面的状态都已经枚举过。
完成状态
已完成
标签：le,题目,trees,How,枚举,二叉树,CF9D From： https://www.cnblogs.com/OIerBoy/p/17448176.html