首页 > 试题广场 >

跳台阶

[编程题]跳台阶

热度指数：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)

C/C++

绒绒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叭！

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

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

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

可以用组合数学推导：

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

我想问下各位大佬，是不是不考虑输入0时为0，也可以通过，我直接傻了

发表于 2021-12-02 15:37:23 回复(0)

Java

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

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

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)

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

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号

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

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

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)