前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。
由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。
已知深渊有 N 层台阶构成 ，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)，请你编程告诉月神，月神有多少种方法爬出深渊
数据范围： 
，输入的数据组数满足 
[编程题]魔法深渊
精华题解
题目难度：二星 考察点：动态规划、预处理 方法1：暴力、动态规划 分析： 这个题很像之前的跳台阶：一共有n个台阶，青蛙只能跳1阶或者是2阶，问有多少种跳法？ 跳台阶思路如下: 假设青蛙跳n个台阶的跳法为f(n)那么： 如果第一次跳的是1阶，那么剩下的n-1个台阶
展开全文
题1：一只青蛙一次可以跳上1级台阶，也可以跳上2级。（排列问题，先后次序不同算不同的结果）
青蛙的第一跳有两种情况，跳一阶和跳二阶。如果跳一阶，则剩下n-1阶就是f(n-1)中跳法；如果挑两阶，则剩下n-2阶就是f(n-2)种情况。所以总情况就是f(n)=f(n-1)+f(n-2);即斐波那契数列。
展开全文
import math
m=int(input())
for _ in range(m):
n=int(input())
if n<4:
print(n) # 小于4层时直接输出
else:
l=[1,2] # n以内2的整数次幂，初始化
展开全文
解法：动态规划（每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)）
递推公式：
for i in range(2, max_m + 1):
k = 1
while i - k >=
展开全文
所有这类跳台阶问题，都可以考虑动态规划，考虑一步怎么到达F(n)=F(n-2^m)+F(n-2^(m-1))+...+F(n-2^0),n>=2^m;注意边界，F(0)=1。然后就是对10e9+3求模了。 import java.util.Scanner;
public class Main
展开全文
问题信息
通过挑战的用户
查看代码-
2022-09-13 16:49:39
-
2022-09-05 21:14:14
-
2022-08-31 22:45:51
-
2022-08-28 17:43:03
-
2022-08-27 18:37:10
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
