二叉树

[编程题]二叉树

热度指数：8063 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小强现在有 $n$ 个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为 $n$ 且树的高度不超过 $m$ 的方案.因为答案很大,所以答案需要模上1e9+7后输出.
树的高度: 定义为所有叶子到根路径上节点个数的最大值.

例如: 当n=3,m=3时,有如下5种方案:

数据范围： $1\le n,m\le 50\$

进阶：时间复杂度 $O(mn^2)\$ ，空间复杂度 $O(nm)\$

输入描述:

第一行输入两个正整数和.

输出描述:

输出一个答案表示方案数.

示例1

输入

3 3

输出

示例2

输入

3 2

输出

示例3

输入

4 3

输出

算法知识视频讲解

Python3

牛客634868734号

def func(a, b, dp):
    return 2*dp[a]*dp[b] if a !=b else dp[a]*dp[b]

mod = 10 ** 9 + 7
node, layer = list(map(int, input().split()))
dp = [0] * (node + 1)
dp[0] = 1

for i in range(1, layer+1):
    bkup = dp[:]
    for j in range(1, min(2**i, node+1)):
        a, b = 0, j-1
        ans = 0
        while a<=b:
            ans += func(a, b, bkup)
            a += 1
            b -= 1
        dp[j] = ans % mod
print(dp[-1])

压缩dp空间

发表于 2024-08-31 01:23:06 回复(0)