### 计算给定高度 K 和节点数 N 的完全二叉树的不同形态数量 对于给定的高度 \( K \) 和节点数 \( N \)，要计算不同的完全二叉树形态数量，可以通过动态规划的方法来解决这个问题。以下是详细的解释和 Python 实现。 #### 动态规划方法 为了求解此问题，定义 `dp[h][n]` 表示高度为 h 并且有 n 个节点的完全二叉树的数量。通过分析可知： - 如果左子树的高度等于当前树的高度减去 1，则右子树的最大高度也应小于或等于当前树的高度减去 1； - 否则，如果左子树的高度正好比当前树少两层，则意味着右子树必须恰好达到最大可能的高度即当前树高减一的情况； 因此可以根据上述逻辑构建状态转移方程并填充表格完成计数过程[^1]。 ```python def num_of_complete_binary_trees(K, N): # 初始化 dp 数组 dp = [[0] * (N + 1) for _ in range(K + 1)] # 边界条件处理 for k in range(1, K + 1): dp[k][0] = 1 for n in range(N + 1): dp[0][n] = 0 dp[0][0] = 1 # 填充 dp 表格 for height in range(1, K + 1): for nodes in range(1, N + 1): max_left_nodes = pow(2, height - 1) - 1 if nodes <= max_left_nodes + 1: dp[height][nodes] += sum(dp[height - 1][:nodes]) elif nodes >= max_left_nodes + 2 and nodes <= 2 * max_left_nodes + 1: min_right_nodes = nodes - max_left_nodes - 1 dp[height][nodes] += ( sum(dp[height - 1][min_right_nodes:]) * sum(dp[height - 2][:max_left_nodes + 2 - min_right_nodes]) ) result = sum([sum(row[:N + 1]) for row in dp[:-1]]) return result % (10 ** 9 + 7) print(num_of_complete_binary_trees(3, 5)) ``` 这段代码实现了基于动态规划算法来统计具有特定高度和节点数目范围内的所有合法完全二叉树结构总数的功能。