首页 > 试题广场 >

跳台阶

[编程题]跳台阶
  • 热度指数：1074727 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：
要求：时间复杂度： ，空间复杂度：
示例1

输入

2

输出

2

说明

青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2
示例2

输入

7

输出

21
算法知识视频讲解
添加回答
推荐
dangle头像 dangle

对于本题,前提只有 一次 1阶或者2阶的跳法。

a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);

b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)

c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) 

d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

e.可以发现最终得出的是一个斐波那契数列：

        

              | 1, (n=1)

f(n) =     | 2, (n=2)

              | f(n-1)+f(n-2) ,(n>2,n为整数)
public class Solution {
    public int jumpFloor(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else if (target ==2) {
            return 2;
        } else {
            return  jumpFloor(target-1)+jumpFloor(target-2);
        }
    }
}


编辑于 2015-06-17 21:21:45 回复(72)
Python 3
ui=f(data)头像 ui=f(data)
from contextlib import nullcontext
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param number int整型
# @return int整型
#
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        a, b, s = 0, 0, 1
        for i in range(1, number+1):
            a, b = b, s
            s = a + b
        return s
编辑于 2024-03-08 01:09:42 回复(0)
Python 3
牛客230443569号头像 牛客230443569号
使用递归+python自带装饰器lru_cache来优化 
import functools


class Solution:
    @functools.lru_cache
    def jumpFloor(self, number: int) -> int:
        # write code here
        if number <= 1:
            return 1
        return self.jumpFloor(number - 1) + self.jumpFloor(number - 2)

发表于 2023-05-13 18:37:09 回复(0)
Python 3
2022a头像 2022a
求指教，输出结果里面有个stdout是个啥情况呀：

发表于 2022-12-05 17:31:34 回复(0)
Python 3
JianYue头像 JianYue 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def jumpFloor(self , number: int) -> int:
        if number < 2:
            return 1
        s0, s1 = 1, 1 # 定义起始值
        step = 2
        while step < number:
            tmp = s0
            s0 = s1
            s1 = s1 + tmp
            step = step + 1
        return s0 + s1

发表于 2022-09-13 15:33:15 回复(0)
Python 3
大头鱼8431头像 大头鱼8431
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        x = 1
        y = 2
        if number == 1:
            return 1 
        elif number == 2:
            return 2
        else:
            # 斐波那契数列的两个数存储形式, 用递归则会在n>30超时
            for i in range(2, number):
                x, y = y, x+y
        return y
发表于 2022-08-31 16:44:36 回复(0)
Python 3
准备回家种田的程序猿头像 准备回家种田的程序猿 
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        if number==1:return 1
        if number==2:return 2
        a,b=1,2
        for i in range(number-2):
            a,b=b,a+b
        return b

发表于 2022-08-14 17:31:51 回复(0)
Python 3
来个offer叭！头像 来个offer叭！ 
class Solution:
    def jumpFloor(self , number: int) -> int:
        # 初始化dp数组
        dp = [0, 1, 2]
        # 遍历生成dp数组
        for i in range(3, number+1):
            dp.append(dp[i-1] + dp[i-2])
        return dp[number]

发表于 2022-07-30 17:13:12 回复(0)
Python 3
东方佑头像 东方佑 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#  规律是斐波那契序列从第二个数开始的序列
class Solution:
    def jumpFloor(self , number: int) -> int:
        
        if number==2:
            return 2
        elif number==1:
            return 1
        else:
#           递归
#             return self.Fibonacci(n-1)+self.Fibonacci(n-2)
            start=[1,1]
            for _ in range(number-1):
                start.append(start[0]+start[1])
                start.pop(0)
            return start[-1]
        

发表于 2022-07-26 15:58:01 回复(0)
Python 3
lun__头像 lun__ 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型

class Solution:
    def jumpFloor(self , number: int) -> int:
        ## 通过递归来实现 
        # write code here
        if number == 0: 
            return 0 
        if number == 1: 
            return 1
        if number == 2: 
            return 2 
        return self.jumpFloor(number-1) + self.jumpFloor(number-2)
    
class Solution:
    def jumpFloor(self , number: int) -> int:
        ## 使用dp动态规划完成本题目 
        #### 当等于1时候，会有超出下标当情况，因此需要判断等于与1的情况
        n = number 
        dp = [0] * (n + 1) 
        dp[0] = 0 
        dp[1] = 1 
        dp[2] = 2
        for i in range(3, n+1): 
            dp[i] = dp[i-1] + dp[i-2] 
        return dp[n] 
        
class Solution:
    def jumpFloor(self , number: int) -> int:
        ## 加入限制条件的动态规划 
        n = number 
        dp = [0] * (n + 1) 
        dp[0] = 0 
        dp[1] = 1 
        if n == 1: 
            return dp[1] 
        else: 
            dp[2] = 2
            for i in range(3, n+1): 
                dp[i] = dp[i-1] + dp[i-2] 
            return dp[n] 

发表于 2022-07-16 10:09:30 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    dp = [1 for i in range(50)]
    def jumpFloor(self , number: int) -> int:
        for i in range(2, number+1):
            self.dp[i] = self.dp[i-1] + self.dp[i-2]
        return self.dp[number]
class Solution:
    def jumpFloor(self , number: int) -> int:
        a, b, c = 1, 1, 1
        for i in range(2, number + 1):
            a = b 
            b = c 
            c = a + b
        return c
发表于 2022-05-11 15:31:42 回复(0)
Python 3
给我吃一口西瓜头像 给我吃一口西瓜
#构造斐波那契数列，直接带入number号
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        a=[0]*41
        a[0]=1
        a[1]=1
        for i in range(2,41):
            a[i]=a[i-1]+a[i-2]
        return a[number]
            
发表于 2022-04-20 15:27:16 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        d = {1:1, 2:2}
        for n in range(3, number+1):
            d[n] = d[n-1] + d[n-2]
        return d[number]

发表于 2022-04-19 14:33:10 回复(0)
Python 3
我是赵同学头像 我是赵同学
也可以不使用动态规划
直接计算n里有几个2,然后计算这些2出现的组合数 
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        def F(n,end=1):
            if n==end:
                return end
            return n*F(n-1,end)
        def Comb(m,n):
            if n==m or m==0:
                return 1
            a = F(m)
            b = F(n,n-m+1)
            return int(b/a)
        n = number//2
        s=0
        for i in range(0,n+1):
            s+=Comb(i,number-2*i+i)
        return s


编辑于 2022-04-09 11:39:55 回复(0)
Python 3
一只兔子的奇幻之旅头像 一只兔子的奇幻之旅 
class Solution:
    def jumpFloor(self , number: int) -> int:
        if number==1:
            return 1
        elif number==2:
            return 2
        else:
            arr=[0]*(number+1)
            arr[0]=0
            arr[1]=1
            arr[2]=2
            for i in range(3,number+1):
                arr[i]=arr[i-1]+arr[i-2]
            return arr[-1]

发表于 2022-04-01 18:49:37 回复(0)
Python 3
DTO头像 DTO
递归虽然可以解，但是总是超时
发表于 2022-03-19 15:53:04 回复(1)
Python 3
空藍性忘头像 空藍性忘
Python直接递归会超时，因为存在大量重复计算，加个备忘录把计算过的结果记录下来，避免重复计算 
class Solution:

    # 递归备忘录，避免重复计算
    dct = {}

    def jumpFloor(self, number: int) -> int:

        # 如果备忘录中保存了计算结果，就直接取
        if number in self.dct.keys():
            return self.dct[number]
        
        else:
            if number == 1:
                return 1
            if number == 2:
                return 2
            res = self.jumpFloor(number - 1) + self.jumpFloor(number - 2)
            self.dct[number] = res # 保存结果到备忘录
            return res


发表于 2022-03-19 01:38:52 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 递归
难度：
50条回答 187958浏览

热门推荐

通过挑战的用户

查看代码

相关试题

跳台阶

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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