首页 > 试题广场 >

爬楼梯2

[编程题]爬楼梯2
  • 热度指数：6472 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
在你面前有一个n阶的楼梯(n>=100且n<500)，你一步只能上1阶或3阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯（到最后一层为爬完）。
(注意超大数据)

输入描述:
一个正整数，表示这个楼梯一共有多少阶


输出描述:
一个正整数，表示有多少种不同的方式爬完这个楼梯
示例1

输入

100

输出

24382819596721629

备注:
注意时间限制
算法知识视频讲解
添加回答
Python
卷积神经网络哦头像 卷积神经网络哦
python的int型无限大(只要内存够) 因此这种题python是最好的选择
简单的动态规划 
arr = [0 for i in range(int(input()) + 1)]
arr[0], arr[1], arr[2] = 1, 1, 1
for i in range(3, len(arr)):
    arr[i] = arr[i-1] + arr[i-3]
print(arr[-1])


发表于 2019-12-26 11:59:29 回复(0)
Python
Sheerloock头像 Sheerloock 
import sys
def diffroad(n):
    # n<3  索引位置：n-1
    # n>=3  索引位置：(n-1)%3
    res = [1,1,2]
    if n<3:
        return 1
    if n==3:
        return 2
    # f(n) = f(n-1)+f(n-3）
    for i in range(4,n+1):
        res[(i-1)%3] += res[(i+1)%3]
    return res[(n-1)%3]

if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    print(diffroad(n))
    

编辑于 2019-09-07 22:34:25 回复(0)
Python
jamke头像 jamke

【企业真题】【小米】爬楼梯2

思路：

    使用排列组合（杀死脑细胞），考虑一次跳3级，两次跳3级，......以此类推

代码：

     
import sys

try:
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break
        n=int(line)
        if 100<=n<500:
            sum=0
            for i in range(1,n//3):
                res=1
                for j in range(2*i,3*i):
                    res*=(n-j)
                for k in range(1,i+1):
                    res//=k
                sum+=res
            if n%3==0:
                sum+=2
            elif n%3==1:
                sum+=n//3+2
            else:
                res=1
                for i in range(1,n//3+1):
                    res=res*(n//3+3-i)//i
                sum+=res+1
            print(sum)
except:
    pass


参考评论区的思路：

    找规律，发现：f(n)=f(n-1)+f(n-3)

代码：

     
line = input()
if line == '':
    print(None)
n = int(line)
if 100 <= n < 500:
    a = [1, 1, 2]
    for _ in range(n-3):
        a = [a[1], a[2], a[0] + a[2]]
    print(a[2])


发表于 2019-08-22 17:20:32 回复(0)
Python
北雷北雷头像 北雷北雷

大数题用python很犯规，引入滚动数组

steps = int(input())

count = [1,1,2]
for i in range(4,steps+1):
    temp = count[0]+count[2]
    count[0] = count[1]
    count[1] = count[2]
    count[2] = temp

print(count[-1])
发表于 2019-08-07 15:07:51 回复(0)
Python
nbgao头像 nbgao 
n = int(input())
a = [0]*(n+1)
for i in range(3):
    a[i] = 1
for i in range(3, n+1):
    a[i] = a[i-1] + a[i-3]
print(a[n])

发表于 2019-07-31 23:22:53 回复(0)
Python
ElonB头像 ElonB 
"""
台阶问题考虑动态规划
每次仅可往上爬1或3级台阶
当前台阶方法数 = 所有一次可到达当前台阶方法数的和
dp[n] = dp[n-1]+dp[n-3]  ( n-t>=0,dp[0]=1 )
"""
if __name__ == "__main__":
    n = int(input().strip())
    dp = [1, 1, 1]
    for i in range(3, n + 1):
        dp.append(dp[i - 1] + dp[i - 3])
    print(dp[n])

发表于 2019-07-16 11:54:47 回复(1)
提交观点

问题信息

动态规划 运维工程师 小米集团 2019 递归
来自：小米2019秋招运维工...
上传者：小小
难度：
6条回答 10131浏览

热门推荐

通过挑战的用户

查看代码

相关试题

爬楼梯2

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号