魔法深渊

[编程题]魔法深渊

热度指数：12474 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。

由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。

已知深渊有 N 层台阶构成，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)，请你编程告诉月神，月神有多少种方法爬出深渊

数据范围： $1 \le n \le 1000 \$ ，输入的数据组数满足 $1 \le m \le 1000 \$

输入描述:

输入共有M行

第一行输入一个数M表示有多少组测试数据，

接着有M行，每一行都输入一个 N 表示深渊的台阶数

输出描述:

输出可能的爬出深渊的方式

示例1

输入

输出

备注:

为了防止溢出，可将输出对10^9 + 3取模

算法知识视频讲解

Python

zcl_zc

# d[n] = d[n-1] + d [n-2] + d[n-4]+...+d[n-t] (t= 2**i=1,2,3...,t<=n)
# d[n-1] 表示最后一步步长为1时的情况
# d[n-2] 表示最后一步步长为2时的情况
# .......
m = int(input())
n = []
mod = 10 **  9 +3
for i in range(m):
    n.append(int(input()))
l = max(n)
d =[1] + [0] * l

for i in range(1,l+1):
    t = 1
    while t <= i:
        d[i] += d[i - t]
        d[i] %= mod
        t *= 2
for i in n:
    print(d[i])

发表于 2019-08-09 17:45:13 回复(0)

Python

ElonB

"""
台阶问题考虑动态规划
每次仅可往上爬2的整数次幂个台阶(1、2、4、....)
当前台阶方法数 = 所有一次可到达当前台阶方法数的和
dp[n] = dp[n-1]+dp[n-2]+dp[n-4]+... ( n-t>=0,dp[0]=1 )
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    m = int(input().strip())
    mod = 1000000003
    dp = [0] * 1001
    dp[0] = 1
    for i in range(1, 1001):
        t = 1
        while t <= i:
            dp[i] += dp[i - t]
            dp[i] %= mod
            t = t * 2
    for _ in range(m):
        n = int(input().strip())
        print(dp[n])

发表于 2019-07-05 13:24:48 回复(7)