首页 > 试题广场 >

跳台阶

[编程题]跳台阶
  • 热度指数：1075290 时间限制：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)
C/C++
绒绒Alice头像 绒绒Alice
比较倾向于找规律的解法，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5，  可以总结出f(n) = f(n-1) + f(n-2)的规律，但是为什么会出现这样的规律呢？假设现在6个台阶，我们可以从第5跳一步到6，这样的话有多少种方案跳到5就有多少种方案跳到6，另外我们也可以从4跳两步跳到6，跳到4有多少种方案的话，就有多少种方案跳到6，其他的不能从3跳到6什么的啦，所以最后就是f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。 
class Solution {
public:
    int jumpFloor(int number) {
        if (number <= 0) {
            return 0;
        }
        if (number == 1) {
            return 1;
        }
        if (number == 2) {
            return 2;
        }
        int first = 1, second = 2, third = 0;
        for (int i = 3; i <= number; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
};
编辑于 2016-10-25 14:12:25 回复(62)
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)
C++
已注销头像 已注销 
    int jumpFloor(int number) {
        if(1 == number)return 1;
        if(2 == number)return 2;
        int a = 2, b = 1;  
        for(int i = 2; i <number; ++i)
        {
            a = a + b;
            b = a - b;
        }
        return a;
    }

发表于 2022-07-28 22:36:44 回复(1)
Java
BlueProtocol头像 BlueProtocol 
public class Solution {
    public int jumpFloor(int target) {
  if(target < 0) {
   throw new IllegalStateException();
  }
  int toFloorOneMethods = 1;
  int toFloorTwoMethods = 2;
  int result = 0;
  if(target == 1) {
   return toFloorOneMethods;
  }
  if(target == 2) {
   return toFloorTwoMethods;
  }
 
  for (int i = 3; i <= target; i++) {
   result = toFloorOneMethods + toFloorTwoMethods;
   toFloorOneMethods = toFloorTwoMethods;
   toFloorTwoMethods = result;
  }
  return result;
    }
}

发表于 2022-07-28 13:42:03 回复(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)
TypeScript
写前端的刻猫猫头像 写前端的刻猫猫 
export function jumpFloor(number: number): number {
    
    // write code here
    if(number <= 0){
        return 0;
    }
    if(number === 1){
        return 1;
    }
    if(number === 2){
        return 2;
    }
    let first:number = 1,second:number = 2 ,third:number = 0;
    for(let i = 3; i <= number;i++){
        third = first + second;
        first = second;
        second = third;
    }
    return third
}


发表于 2022-02-23 23:12:16 回复(0)
Python 3
Erfinder头像 Erfinder
可以用组合数学推导：
1. 如果全只跳一步，则方式有C（number, 0）= 1 种；
2. 如果有1次跳两步，其他都跳一步，则方式有 C(number-1, 1)  种；
3. 如果有 i 次跳两步，其余跳一步，其中 i <= number/ / 2，则方式有 C(number - i , i ) 种；
4. 叠加
import math
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        n = number // 2
        i = 0
        Sum = 0
        if number == 0:
            return 0
        for i in range(n+1):
            term = math.factorial(number-i) / math.factorial(i) / math.factorial(number-i-i)
            #组合数公式，m+n = number, i<=number/2
            Sum += term
        return int(Sum)
发表于 2022-01-01 22:48:48 回复(0)
C++
笨小孩ovo头像 笨小孩ovo
我想问下各位大佬，是不是不考虑输入0时为0，也可以通过，我直接傻了
发表于 2021-12-02 15:37:23 回复(0)
Java
牛客518952345号头像 牛客518952345号
//可以跑，但很耗时间（#光速逃离）
public class Solution {
    public int jumpFloor(int target) {
        if(target<=0) return 0;
        if(target<=3) return target;
        return jumpFloor(target-1)+jumpFloor(target-2);
    }
}
发表于 2021-11-29 09:08:36 回复(0)
Java
不爱吃烤肠头像 不爱吃烤肠
对于这题,没什么多说的 
int[] arr = new int[]{0,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141};
        return arr[target];


发表于 2021-10-08 22:18:24 回复(1)
Java
together"头像 together" 
public class Solution {

    // f(n) = f(n-1) + f(n-2)， 代表最后一次跳一步和最后一次跳两步的跳法之和
    // f(1) = 1, f(2) = 2, 注意不要从f(0)开始, f(0)没有意义
    public int jumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        int pre1 = 2, pre2 = 1, ans = 0;
        for (int i = 3; i <= target; i++) {
            ans = pre1 + pre2;
            pre2 = pre1;
            pre1 = ans;
        }
        return ans;
    }
}

发表于 2021-08-06 09:59:28 回复(0)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
class Solution:
    def jumpFloor(self, number):
        if number <= 3:
            return number
        num1, num2 = 2, 3
        for _ in range(number-3):
            num2 += num1
            num1 = num2 - num1
        return num2

发表于 2021-07-31 08:18:04 回复(0)
C
CrescentHU头像 CrescentHU
int jumpFloor(int n) {
    int f1,f2,f3,i;
    f1=f2=1;
    if(n==0||n==1)return n;
    for(i=2;i<=n;i++)
    {
        f3=f1+f2;
        f1=f2;
        f2=f3;
    }
    return f3;
}
发表于 2021-07-24 17:12:57 回复(0)
Java
梦幻一跃头像 梦幻一跃 
import java.math.BigDecimal;
public class Solution {
    
    //第一次的解法：暴力破解、去重（如果不用BigDecimal，数字会存不下），效率一般，超高耗内存
    public int jumpFloor(int target) {
        BigDecimal ans = BigDecimal.ZERO;
        for(int i=0; i<=target; i++){
            for(int j=0; j<=target/2+1; j++){
                if(i+2*j==target){
                    BigDecimal n = dfsOrder(BigDecimal.valueOf((long)(i+j)), BigDecimal.valueOf(2), BigDecimal.valueOf(1));
                    if(i>1){
                        n = n.divide(dfsRepeat(BigDecimal.valueOf(i),BigDecimal.ONE,BigDecimal.ONE), 0, BigDecimal.ROUND_DOWN);
                    }
                    if(j>1){
                        n = n.divide(dfsRepeat(BigDecimal.valueOf(j),BigDecimal.ONE,BigDecimal.ONE), 0, BigDecimal.ROUND_DOWN);
                    }
                    ans = ans.add(n);
                }
            }
        }
        return ans.intValue();
    }

    /**
     * 数字的不同的排列结果
     * @param n
     * @return
     */
    public BigDecimal dfsOrder(BigDecimal n, BigDecimal start, BigDecimal ans){
        if(start.compareTo(n) > 0){
            return ans;
        }
        ans = start.multiply(ans);
        return dfsOrder(n, start.add(BigDecimal.valueOf(1)), ans);
    }
    //去除重复计算的方式
    public BigDecimal dfsRepeat(BigDecimal num, BigDecimal start, BigDecimal ans){
        if(start.compareTo(num) > 0){
            return ans;
        }
        ans = start.multiply(ans);
        return dfsRepeat(num, start.add(BigDecimal.valueOf(1)), ans);
    }
}
哎.. 
    //第二种解法 斐波那契数列
    public int jumpFloor(int target) {
        return fibonacci(target, 1, 1);
//         return fibonacci(target);
    }
    
//     //普通递归，效率差，耗内存
//     public int fibonacci(int n){
//         if(n<=1){
//             return 1;
//         }
//         return fibonacci(n-1)+fibonacci(n-2);
//     }
    
    //尾递归，效率高，耗内存
    public int fibonacci(int n, int pre, int curr){
        if(n <= 1){
            return curr;
        }
        return fibonacci(n-1, curr, pre + curr);
    }

//轮询大法
    public int jumpFloor(int target) {
        if(target <= 3){
            return target;
        }
        int pre = 1;
        int curr = 1;
        while(target >= 2){
            int temp = curr;
            curr = pre + curr;
            pre = temp;
            target--;
        }
        return curr;
    }


编辑于 2021-04-18 23:13:58 回复(0)
wengJJ头像 wengJJ
Python
求解斐波那契数列 
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
#         迭代写法
        if number <= 1:
            return number
        pre_n = 0
        n = 1
        for _ in range(number):
            total = pre_n + n
            pre_n = n
            n = total
        return total
#         递归写法 内存溢出
#         if number <= 2:
#             return number
#         return self.jumpFloor(number-1)+self.jumpFloor(number-2)


发表于 2021-04-17 17:50:23 回复(0)
牛客401731755号头像 牛客401731755号 
function jumpFloor(number)
{
    // 定义一个数组，用空间换时间
    var tempArr = [,1,2]
    
    // 使用递归，第n个台阶有两种方式，跳一个从n-1跳上来，跳两个从n-2跳上来
    function tempFun (number) {
        if (tempArr[number]) {
            return tempArr[number]
        } else {
            tempArr[number] = tempFun(number - 1) + tempFun(number - 2)
            return tempArr[number]
        }
    }
    return tempFun (number)
}
module.exports = {
    jumpFloor : jumpFloor
};

发表于 2021-04-13 14:55:20 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function jumpFloor(number)
{
    // write code here
    var dp = [];
    dp[0] = dp[1] = 1;
    for(var i = 2;i<=number;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[number];
}

发表于 2021-03-16 17:41:26 回复(0)
一缕阳光·脱离地心引力头像 一缕阳光·脱离地心引力
这编辑器有鬼了，方法名得改成大写开头。

Java 1，递归，随着参数增大效率急剧降低: 
public class Solution {
    int jumpFloor(int number) {
        if (number <= 1) return 1;
        if (number == 2) return 2;
        return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
}
Java 2，非递归： 
class Solution {
    public int jumpFloor(int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int a = 1, b = 2, sum = a + b;
        for (int i = 3; i < n; i++) {
            a = b;
            b = sum;
            sum = a + b;
        }
        return sum;
    }
}

编辑于 2021-02-03 15:26:21 回复(0)
C/C++
MooNNooM头像 MooNNooM 
class Solution {
public:
    int nums;
    void dec(int x){
        if(x-1==0){
            nums++;
            return;
        }else if(x-2==0){
            nums+=2;
            return;
        }else{
            dec(x-1);
            dec(x-2);
        }
    }
    int jumpFloor(int number) {
        nums=0;
        dec(number);
        return nums;
    }
};
把问题看成一棵二叉树，往左走是减一，往右走是减二，如此一来，叶节点个数就是跳法数。
特别的，当减到某个结点是2时，下面必然有两个叶节点，故nums+=2。当减到为1时，nums+=1。
发表于 2021-01-19 19:34:05 回复(0)
不经历怎么能成长头像 不经历怎么能成长 
/*
f[n]:跳n台阶的种类数=跳n-1台阶的种类数+跳n-2台阶的种类数
f[n]=f[n-1]+f[n-2]
f[1]=1
f[2]=2
f[3]=3
*/
class Solution {
public:
    int jumpFloor(int number) {
        int a=1,b=2;//求f[n]只保存两个数即可。
        while(--number){
            b = a+b;
            a = b-a;
        }
        return a;
    }
};
//时间复杂度为O(n)，空间复杂度为O(1)


发表于 2021-01-06 20:57:05 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

跳台阶

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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