题解 | 小红蹦跳蹦跳

import sys


n = int(input())

# 初始化左脚可到达的台阶的动态规划数组
# left[i] 表示到达第i级台阶时，最后一步是左脚（走奇数步）的方法数
# 初始状态：
# left[0] = 0：第0级台阶（起点），左脚未迈步，方法数为0
# left[1] = 1：第1级台阶，只能用左脚走（第一步），方法数为1
# left[2] = 0：第2级台阶，最后一步不可能是左脚（第二步必须用右脚），方法数为0
left = [0, 1, 0]

# 初始化右脚可到达的台阶的动态规划数组
# right[i] 表示到达第i级台阶时，最后一步是右脚（走偶数步）的方法数
# 初始状态：
# right[0] = 0：第0级台阶（起点），右脚未迈步，方法数为0
# right[1] = 0：第1级台阶，最后一步不可能是右脚（第一步必须用左脚），方法数为0
# right[2] = 1：第2级台阶，只能用右脚走（第二步），方法数为1
right = [0, 0, 1]

# 结果取模的模数，改为整数类型避免浮点数精度问题
Mod = 10**9 + 7

# 从第3级台阶开始，递推计算每一级的方法数
for i in range(3, n + 1):
    # 计算到达第i级台阶最后一步是左脚的方法数：
    # 情况1：上一步（到i-1级）是右脚，再走一步（左脚再走一级）到i级
    # 情况2：上两步（到i-2级）是左脚，走两步(右左)直接到i级
    # 两种情况相加后取模
    left.append(((right[i-1] + left[i-2]) % Mod))
    
    # 计算到达第i级台阶最后一步是右脚的方法数：
    # 情况1：上一步（i-2级）是左脚,再走一步(右脚再走两级)到i级
    # 情况2：上两步（i-2级）是右脚，走两步（左右）跳过一级直接到i级
    # 两种情况相加后取模
    right.append((left[i-2] + right[i-2]) % Mod)

# 最终结果是到达第n级台阶的所有方法数（左脚+右脚），取模后输出整数
print(int((left[-1] + right[-1]) % Mod))