DP无敌

n = int(input())

# 初始化动态规划数组dp，dp[i]表示以数字i结尾的合法数列个数
dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i // 2] + dp[i-1] if i % 2 == 0 else dp[i-1]

print(dp[n])

还是极限时间