首页 > 试题广场 >

跳台阶

[编程题]跳台阶

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

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围： $1 \leq n \leq 40$

要求：时间复杂度： $O(n)$ ，空间复杂度： $O(1)$

示例1

输入

输出

说明

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

示例2

输入

输出

算法知识视频讲解

推荐

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

shenge08

class Solution:
    cache ={}
    def jumpFloor(self , number: int) -> int:
        if number == 1:
            self.cache[number] = 1
            return 1
        if number == 2:
            self.cache[number] = 2
            return 2
        # 第一步走一步
        if number-1 not in self.cache.keys():
            x = self.jumpFloor(number-1)*1
        else:
            x = self.cache[number-1]
        # 第一步走两步
        if number-2 not in self.cache.keys():
            y = self.jumpFloor(number-2)*1
        else:
            y = self.cache[number-2]
        self.cache[number] = x+y
        return x+y;
        # write code here

跳n级台阶：第一步只有 1级或者2级台阶

第一步走1级，还剩n-1级要走求f(n-1）

第一步走2级，还剩n-2级要走求f(n-2)

综上所述：f(n) = f(n-1）+ f(n-2)

发表于 2022-05-18 09:43:16 回复(0)

Python

乐不思蜀201909081752256

class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 2:
            return number
        a = [1, 2]
        for i in range(2, number):
            a.append(a[-1] + a[-2])
        return a[-1]

发表于 2021-07-13 00:08:37 回复(0)

Python

不愿吃饼的三文鱼很调皮

class Solution:
    def jumpFloor(self, number):
        if number < 2: return number
        if number == 2: return 2
        res = [1, 1]
        if number > 2:
            for i in range(number):
                res.append(res[-1] + res[-2])
        return res[number]

发表于 2021-07-09 18:30:09 回复(0)

Python

kotoriii

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        def jiecheng(n):
            m=1
            for i in range(n):
                m=m*(i+1)
            return m
        tjsl2=0
        tjsl1=0
        solu=0
        for i in range(int(number/2)+1):
            tjsl2=i
            tjsl1=number-2*i
            solu=solu+jiecheng(tjsl1+tjsl2)/(jiecheng(tjsl1)*jiecheng(tjsl2))
        return solu
        # write code here

笨比的排列组合解法

发表于 2021-06-06 11:10:38 回复(0)

Python

Arsent

fibnaci

# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
fib = [1,1]
for i in range(1, number):
fib.append(fib[i]+fib[i-1])
return fib[-1]

发表于 2021-05-02 16:54:42 回复(0)

Python

牛客诶谁

class Solution:
def jumpFloor(self, number):
if number == 0 or number == 1:
return 1
lst = [1]*(number+1)
for i in range(2, number+1):
lst[i] = lst[i-1] + lst[i-2]
return lst[number]

发表于 2021-04-24 15:19:26 回复(0)

Python

牛客541273514号

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        res=[0,1,2,3]
        if number<=3:
            return res[number]
        else:
            for i in range(4,number+1):
                res.append(res[i-1]+res[i-2])
            return res[number]

发表于 2021-04-11 23:48:40 回复(0)

Python

風呂

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        a = 0
        b = 1
        c = 0 
        for i in range(1,number + 1):
            c = a + b
            a = b
            b = c
        return c

斐波那契，yyds

发表于 2021-03-11 20:14:42 回复(0)

Python

牛客952747261号

# -*- coding:utf-8 -*-

#解题思路就是求一个二元一次方程n=2*x+y所有整数解的个数，以及排列组合的问题，对于递归法和迭代法小弟不懂。

class Solution:
def jumpFloor(self, number):
N=0
n=number
for x in range(0,n+1):
if n%2==1:
for y in range(0,int((n+1)/2)):
if n==2*y+x:
if x==0 or y==0:
N+=1
else:
N=N+Solution().sumary(x,y)
else:
for y in range(0,int(1+n/2)):
if n==2*y+x:
if x == 0 or y == 0:
N += 1
else:
N = N + Solution().sumary(x, y)

return N

#阶乘运算

def founc(self,i):
if i==1:
return i
else:

return i*Solution().founc(i-1)

#排列组合

def sumary(self,x,y):
N=Solution().founc(x+y)
M1=Solution().founc(x)
M2=Solution().founc(y)

return int(N/(M1*M2))

#运行时间20ms，占用内存3108K

发表于 2021-03-09 20:24:59 回复(0)

Python

牛客651359151号

核心思想：

f(0) = f(1) = 1

f(n) = f(n-1) + f(n-2)

代码实现：

class Solution:
    def jumpFloor(self, number):
        # write code here
        a = b = res = 1
        for i in range(number-1):
            res = a + b 
            a = b
            b = res
        return res

发表于 2021-02-03 21:50:54 回复(0)

Python

食堂在逃干饭王

其实就是斐波那契数列，也可以用个简单dp。直接递归效率太低。

# -*- coding:utf-8 -*-

class Solution:
    def __init__(self):
        self.dp = [0] * 1001
        
    def jumpFloor(self, number):
        if number < 0:
            return -1
        if number <= 2:
            return number
        if self.dp[number - 1] == 0:
            self.dp[number - 1] = self.jumpFloor(number - 1)
        if self.dp[number - 2] == 0:
            self.dp[number - 2] = self.jumpFloor(number - 2)
        return self.dp[number - 1] + self.dp[number - 2]

发表于 2021-01-31 20:27:06 回复(0)

Python

保洁大哥

# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
F = [0,1,2]
for i in range(3,number+1):
F.append(F[i-1]+F[i-2])
return F[number]

# write code here

动态规划

发表于 2021-01-28 21:41:52 回复(0)

Python

老和山小学生

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        results = [1, 2]
        if number >= 3:
            for i in range(number-2):
                results.append(results[-1]+results[-2])
        return results[number-1]

发表于 2020-10-19 09:56:24 回复(0)

Python

牛客690867866号

# -*- coding:utf-8 -*-
def Combinatorial(n,i):
    Min=min(i,n-i)
    result=1
    for j in range(0,Min):
        result=result*(n-j)/(Min-j)
    return  result
class Solution:
    def jumpFloor(self, number):
        # write code here
        number2=0
        count=0
        while number2*2<=number:
            number1=number-number2*2
            count=count+Combinatorial(number1+number2,number1)
            number2=number2+1
        return count

先计算跳两个台阶的次数number2，和跳一个台阶的次数number1，总次数为number1+number2

所以当前的组合数为C(number1+number2,number2)

最后对所有组合数求和

发表于 2020-09-09 10:13:02 回复(0)

Python

TinD

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number, f1=1, f2=2):
        if number == 1:
            return f1
        else:
            return self.jumpFloor(number-1, f2, f1+f2)

利用尾递归避免栈溢出。解题思路很重要的一点就是看出这是一个类斐波拉契数列！

发表于 2020-09-09 08:16:20 回复(0)

Python

赛博迷航

关于1,2跳台阶的问题

python太慢了，试了三段都是不行：

import numpy as np class Solution: def jumpFloor(self, number):
        path=[[0]]
        n_count=0  for i in path: if sum(i)>=number-1:
                n_count=n_count+1  else:
                tmp=i.copy()
                tmp.append(1)
                path.append(tmp)
                tmp = i.copy()
                tmp.append(2)
                path.append(tmp) return n_count def jumpFloor2(self, number): if number<=1: return 1  else: return self.jumpFloor(number-2)+self.jumpFloor(number-1) def jumpFloor1(self, number):
        path=[[0]]
        steps=iter(path) #next(steps)  n_count=0  try: while True:
                step=next(steps) if sum(step)>=number-1:
                    n_count=n_count+1  else:
                    tmp=copy.copy(step)
                    tmp.append(1)
                    path.append(tmp)
                    tmp = copy.copy(step)
                    tmp.append(2)
                    path.append(tmp) #next(step)  except: pass  finally: return n_count

大家看看，是否有问题

编辑于 2020-08-27 21:40:02 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        array = [0,1,2]
        if number < 3:
            return array[number]
        for i in range(3,number+1):
            array.append(array[i-2]+array[i-1])
        return array[number]

1,该题的规律是0、1、2、3、5、8、13.......后面的数等于前两个数之和，所以从n=3开始可以利用递归的方法

2，array.append()：不断增加数组的元素，但是不要把 i 错写成number；以及range()是取左不取右，所以应该是number+1不是number

3,关于调用的问题：方法写好了之后，我们如何调用呢？

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        array = [0,1,2]
        if number < 3:
            return array[number]
        for i in range(3,number+1):
            array.append(array[i-2]+array[i-1])
        return array[number]

if __name__ == "__main__":
    a = Solution()
    print(a.jumpFloor(5))

则可看到输出“8”：↓

4，如果是直接输出前n种的跳法数：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        array = [0,1,2]
        if number == 0:
            return [array[0]]
        if number == 1:
            return [array[0],array[1]]
        if number == 2:
            return array

        for i in range(3,number+1):
            array.append(array[i-2]+array[i-1])
        return array

if __name__ == "__main__":
    a = Solution()
    print(a.jumpFloor(2))

发表于 2020-07-23 16:17:56 回复(0)

Python

牛客739242922号

用一个笨笨的方法，避免了超时风险

使用一个数组来储存已经计算的值，避免重复计算。

class Solution:
    def jumpFloor1(self, number, res):
        if number <= 1:
            return 1
        elif res[number] != -1:
            return res[number]
        else:
            res[number] = self.jumpFloor1(number - 1, res) + self.jumpFloor1(number - 2, res)
            return res[number]
    def jumpFloor(self, number):
        res = [-1] * (number + 1)
        return self.jumpFloor1(number, res)

发表于 2020-06-15 11:28:56 回复(0)

Python

hello嘞

class Solution:
def jumpFloor(self, number):
def jiecheng(n): #求阶乘
sum = n
if n==0:
return 1
else:
while n>1:
sum = sum*(n-1)
n -= 1
return sum
def C_n_m(n,m): (3508)#用排列组合
result = jiecheng(m)/(jiecheng(n)*jiecheng(m-n))
return int(result)
sum = 0
a = 1
b = 2
for i in range(number+1):
for j in range(number):
if a*i+b*j == number: #最后的结果一定满足1*i + 2* j ==阶数，当i、j有一个不为0时，即i个1 和j个2排列组合，看多少种情况；否则就一种情况，直接加1
if i or j:
sum += C_n_m(i,i+j)
else:
sum += 1
return sum

发表于 2020-03-24 13:44:13 回复(0)

Python

201905242154668

跳台阶(理论+python实现)

1.理论

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解决跳台阶问题，为了方便理解和观察出规律，我们先自己点出n=1,2,3,4,5时所对应的规律：

当n=1时，只有1种跳法，即 $f(1)=1$ ；
当n=2时，有2种跳法，即 $f(2)=2$ ；
当n=3时，有3种跳法，即 $f(3)=3$ ；
当n=4时，有5种跳法，即 $f(4)=5$ ；
当n=5时，有8种跳法，即 $f(5)=8$ ；

如何计算跳法呢？

简单来说，就是不断采用每次跳1级，还是跳2级来组合，所有可能的组合都是一种跳法。

总结上面分析的跳台阶的规律：

f(1)=1
f(2)=2
f(3)=3, f(3)=f(1)+f(2)
f(4)=5, f(4)=f(2)+f(3)
f(5)=8, f(5)=f(3)+f(4)
......

得出它们的通项公式如下：

$f(1)=1$

$f(2)=2$

$f(n)=f(n-1)+f(n-2),n>=3$

由通项公式来看，这是一个典型的递归求解问题，简单粗暴来讲，递归就是不断依靠之前的函数值来运算得到当前值的过程。

2.python实现

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        # -----------------------------
        # 增加代码鲁棒性
        if number == 1:
            return 1
        if number == 2:
            return 2
        # -----------------------------
        # 实际应用
        fone,ftwo,total=1,2,0
        for i in range(3,number+1):
            # 观察规律
            #f(1)=1
            #f(2)=2
            #f(3)=3, f(3)=f(1)+f(2)
            #f(4)=5, f(4)=f(2)+f(3)
            #f(5)=8, f(5)=f(3)+f(4)
            # ......
            total=fone+ftwo
            fone,ftwo=ftwo,total  # 不断更新前一项、前前一项的值
        return total

发表于 2020-02-19 14:16:38 回复(0)

提交观点

问题信息

动态规划记忆化搜索递归

难度：

90条回答 3482收藏 185405浏览

通过挑战的用户

查看代码

牛客97646...

2023-03-11 09:45:28
Avacado~

2023-03-05 11:49:02
章思思

2023-02-10 10:00:21
牛客30382...

2022-12-21 11:56:14
想熬夜的少年a...

2022-12-11 14:28:21

跳台阶

输入

输出

说明

输入

输出

跳台阶(理论+python实现)

1.理论

2.python实现

问题信息

热门推荐

通过挑战的用户

相关试题