题解 | 小红的二叉树

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。