10.16腾讯笔试-第五题跳台阶

n级台阶，相邻两次的步数要奇偶性相异，问方法数。
如4级台阶有两种方案：
1+2+1
4

思想就是dp，然后优化下，奇偶项求和不要每次都重新求。
数学逻辑：
记f0(n)为最后一步走偶数步，上n级台阶的方法数
然后f0(n) = f0(n-2) + f0(n-4) + ...
if n是偶数，f0(n)++
同样的定义f1(n)为最后一步走奇数的方法数
有了递推关系，然后dp求解就可以了

代码：
这代码没注释铁定没啥人看得懂吧……

n = int(input().strip())
BIGNUM = 10**9 + 7
# dp = [[None] * (n+1) for _ in range(2)]
dp = [[0,0],[0,0]]
ans = 0
for x in range(1,n + 1):
    f0 = dp[1][x % 2] + (x+1) % 2
    f1 = dp[0][(x+1) % 2] + x % 2
    dp[0][x % 2] += f0
    dp[0][x % 2] %= BIGNUM
    dp[1][x % 2] += f1
    dp[1][x % 2] %= BIGNUM
    if x == n:
        ans = f0+f1

print(ans % BIGNUM)