首页 > 试题广场 >

跳台阶

[编程题]跳台阶

热度指数：1074727 时间限制：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)

Javascript

牛客962430562号

/*
     如果第一次跳一个台阶，后续的跳法有f(n-1)种
     如果第一次跳两个台阶，后续的跳法有f(n-2)种
     因此f(n)=f(n-1)+f(n-2)

     另外，
     当n=1时，f(1)=1
     当n=2时，f(2)=2
     */

    //暴力递归
    const jump01 = (n) => {
      let result = 0
      if(n === 0){
        result = 1
      }else if(n <= 2){
        result = n
      }else if(n > 2){
        result = jump01(n-1) + jump01(n-2)
      }
      return result
    }

    //把计算过的情况存入map，减少计算量
    function jump02(n){
      let map = new Map()
      if(n === 0){
        map.set(n,1)
      }else if(n <= 2){
        map.set(n,n)
      }
      if(map.has(n)){
        return map.get(n)
      }else{
        map.set(n,jump01(n-1) + jump01(n-2))
        return map.get(n)
      }
    }

    //动态规划
    function jump03(n){
      if(n === 0){
        return 1
      }else if(n <= 2){
        return n
      }
      let a = 1,b = 2,temp = 0
      for(let i = 3;i <= n;i++){
        temp = a + b
        a = b
        b = temp
      }
      return temp
    }

发表于 2022-09-01 10:54:11 回复(0)

Javascript

Xinleidebaby

function jumpFloor(number)
{
    // write code here
    let count=0
    function jump(n){
        if(n==number) return count++
        if(n<number){
            jump(n+1)
            jump(n+2)
        }
    }
    jump(0)
    return count
}

发表于 2022-08-05 16:28:30 回复(0)

Javascript

A-成都搬砖日结包吃不包住

function jumpFloor(number)
{
    // write code here
    // 本题比较特殊可以将动态规划的数组优化为两个变量, 但是此处仍采用基础的动态规范方法

    // 1. 确定dp数组意义, 并进行初始条件赋值
    const dp = [1, 2]
    if(number<3) return dp[number-1]

    // 2. 确定元素之间的关系, 由题知: dp[i] = dp[i-1] + dp[i-2]
    let cur = 2

    // 3. 遍历求值
    while(cur<number){
        dp[cur] = dp[cur-1] + dp[cur-2]
        cur++
    }
    return dp[number-1]
}
module.exports = {
    jumpFloor : jumpFloor
};

发表于 2022-03-11 21:39:23 回复(0)

Javascript

牛客537375115号

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

Javascript

嘉然今天恰烧烤

function jumpFloor(number)
{
    // write code here
    if(number === 1) return 1;
    if(number === 2) return 2;
    let dp = [1,2];
    for(let i = 3; i <= number; i++) {
        dp.push(dp[i-2] + dp[i-3]);
    }
    return dp[dp.length-1];
}

发表于 2021-10-25 17:20:07 回复(0)

Javascript

牛客464126931号

1、回溯法

function jumpFloor(number)
{
    let result =0;
    let drawback =function(n){
        if(n==0) { result++; return ;}
        else if(n<0){return ;}
        for(let i=0;i<2;i++){
            n= n-(i+1);
            drawback(n);
            n = n+(i+1);
        }
    }
    drawback(number);
    return result;
}

2、自上而下，n步台阶的解法=n-1解法+n-2解法

function jumpFloor(number)
{
    let result =0;
    let dp1 = 1,dp2 = 2;
    if(number>2){
      for(let i=3;i<=number;i++){
        result = dp1+dp2;
        dp1 = dp2;
        dp2 = result;
      }
      return result
    }else{
      return number;
    }
    
}

发表于 2021-10-12 12:23:21 回复(0)

Javascript

乱不能

//递归

function jumpFloor(number)
{
// write code here
if(number == 1) return 1
if(number == 2) return 2
return jumpFloor(number - 1) + jumpFloor(number - 2)
}
module.exports = {
jumpFloor : jumpFloor
};

//非递归

发表于 2021-09-25 23:50:06 回复(0)

Javascript

yhdgh

function jumpFloor(number){
    var arr=[1,2]
    for(var i=2;i<number;i++){
        arr[i]=arr[i-1]+arr[i-2]
    }
    return arr[number-1]
}

发表于 2021-09-06 13:56:59 回复(0)

Javascript

牛客477650639号

原来每次测出来的时间和空间都不一样，只是简单的用几个例子测一下呀

function jumpFloor(number)
{
    // write code here
    // 基础的类似斐波那契
    // if(number === 1) return 1;
    // if(number === 2) return 2;
    // return jumpFloor(number-1) + jumpFloor(number-2);
    
    // 动态规划
    let g = 1,
        f = 2;
    if(number === 1) return g;
    if(number === 2) return f;
    
    for(; number > 1; number--) {
        f += g;
        g = f - g;
    }
    return g;
}
module.exports = {
    jumpFloor : jumpFloor
};

发表于 2021-08-31 17:14:03 回复(0)

Javascript

十味一心

//动态规划
function jumpFloor(number)
{
    // write code here
    let dp = new Array(number+1).fill(0);
    dp[0]=dp[1]=1;
    for(let i=2;i<=number;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[number];
}
//递归
function jumpFloor(number)
{
    // write code here
    if(number<=1)return 1;
    return jumpFloor[number-1]+jumpFloor[number-2];
}

发表于 2021-08-30 18:59:58 回复(0)

Javascript

小菜鸡的菜

function jumpFloor(number)
{
if(number===1 || number===2){
return number
}
return jumpFloor(number-1)+jumpFloor(number-2)
}

发表于 2021-08-12 22:31:58 回复(0)

JavaScript

白下布衣

高性能递归解法：

这题如果用递归，最大的问题是：一对多递归存在严重的重复递归计算问题。于是我们把每个节点计算结果缓存用Map下来，递归性能非常高，大家试试，觉得好给点个赞

const map = new Map();

function jumpFloor(number)
{
    if(number > 1){
        let result = map.get(number);
        if (result) {
            return result;
        }
        result = jumpFloor(number - 1) + jumpFloor(number - 2)
        map.set(number, result);
        return result
    } else {
        return 1;
    }
}
module.exports = {
    jumpFloor : jumpFloor
};

编辑于 2021-03-30 13:06:10 回复(0)

JavaScript

绿枸杞pari

function jumpFloor(number){

if (number==0||number==1){

return number

}

var stepsum=[1,2];

for(var i=2;i<number;i++){

stepsum.push(stepsum[i-2]+stepsum[i-1])

}

return stepsum[number-1]

}

//不用递归可以快一点

发表于 2021-03-21 15:24:12 回复(0)

JavaScript

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)

JavaScript

splwany

javascript版：

function jumpFloor(number)
{
    if (number <= 1) return number;
    let a = 1, b = 1;
    for (let i = 2; i <= number; i++) {
        b = a + b;
        a = b - a;
    }
    return b;
}

python版：

class Solution:
    def jumpFloor(self, number):
        if number <= 1:
            return number;
        a = b = 1
        for _ in range(2, number + 1):
            a, b = b, a + b
        return b

编辑于 2021-03-05 16:52:11 回复(0)

JavaScript

不进好工作不改名

function jumpFloor(number)
{
    if(number<=2){return number;}
    var a=1,b=1;
     for(let i=1;i<number;i++){
         a=a+b;
         b=a-b;
     }
    return a;
}

发表于 2021-03-01 16:12:17 回复(0)

JavaScript

huyue0802

这道题可以当成一道数学题来做，首先找规律（阶数->方法数）

1->1,2->2,3->3,4->5,5->8

这个规律的数学意义其实是：如果你要跳5阶，那么有两种分类：最后一步跳2，那么前面就有3阶种跳法，最后一步跳1，那么前面就有4阶种跳法。

那么当台阶为n+1阶时，其实是=》第n+1阶跳一阶，剩余n阶的跳法，第n/n+1阶跳两阶，剩余n-1阶的跳法。也就是A[n] = A[n-1]+A[n-2]。

function jumpFloor(number)
{
    // write code here
    let meth = [1, 2, 3];
    for(let i = 3; i < number; i++) {
        meth.push(meth[i-2] + meth[i-1])
    }
    return meth[number - 1]
}

发表于 2020-12-28 16:10:26 回复(0)

JavaScript

别卷啦！

尾递归

function jumpFloor(number)
{
    const fn = (n,temp1 =1,temp2=1) => {
    if(n <= 1) return temp2
    return fn(n-1, temp2,(temp1 + temp2))
    }
    return fn(number)
    // write code here
}

动态规划

function jumpFloor(number)
{
    // write code here
   const dp = new Array(number+1).fill(0)
   dp[0] = 1
   dp[1] = 1
    for(let i = 2; i < dp.length;i++){
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[number]
}

编辑于 2021-06-22 19:23:01 回复(0)

JavaScript

咚咚咚，开门，查水表

function jumpFloor(number)
{
    //一只青蛙一次可以跳上1级台阶，也可以跳上2级。
    //求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
    //对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以F(n) = F(n-1) + F(n-2)
    if (number <= 0) return 0;
    else if (number == 1) return 1;
    else if (number == 2) return 2;
    else return jumpFloor(number-1) + jumpFloor(number-2)
}
module.exports = {
    jumpFloor : jumpFloor
};

发表于 2020-09-13 15:04:20 回复(0)

提交观点

问题信息

动态规划记忆化搜索递归

难度：

46条回答 3629收藏 187957浏览

通过挑战的用户

查看代码

牛客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

跳台阶

输入

输出

说明

输入

输出

高性能递归解法：

问题信息

热门推荐

通过挑战的用户

相关试题