题解 | 小红的二叉树
小红的二叉树
https://www.nowcoder.com/practice/ee287e0f6af64edd969f01444dd763e4
depth = int(input())
dp = [0] * depth
dp[0] = 0
if depth == 1:
print(dp[0])
elif depth == 2:
dp[1] = 1
print(dp[1])
else:
dp[1] = 1
for i in range(2, depth):
dp[i] = dp[i - 1] + 2 ** (i - 1) + 2 ** i
print(dp[-1] % (10 ** 9 + 7))
核心是找到每增加一层，路径数量变化的规律是dp[i] = dp[i - 1] + 2 ** (i - 1) + 2 ** i。
查看17道真题和解析
，这个代码不商用是没问题的