首页 > 试题广场 >

跳台阶

[编程题]跳台阶

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

Java

陈果然

递推出来，比较简单。
public int jumpFloor (int number) {
        if(number <= 2) return number;
 
        return jumpFloor(number - 1) + jumpFloor(number - 2);
    }

发表于 2025-11-25 10:21:23 回复(0)

Java

allin秋招的秋田犬很苦闷

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloor (int number) {
        // write code here
        if(number==1){
            return 1;
        }else if(number==2){
            return 2;
        }
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
}

发表于 2025-10-18 01:12:20 回复(0)

Java

牛客522581807号

第一次觉得 long 能容纳的数字太小了.... 按这种方法溢出了，只能算20步以下的

import java.util.*;


public class Solution {

    public long jiecheng(int x){
        if(x==0){
            return 1;
        }
        long res = 1;
        for(int i = 1;i <= x;i++){
            res *= i;
        }
        return res;
    }

    // 计算详细如何跳跃
    // 可以简化为组合问题， 设 一步的数量为x 两部的数量为y
    // 总共则是从 （x+y）
    //              x
    // 需要一个计算阶乘的函数
    public long checkSolusion(int oneTimes , int twoTimes){
        long res = jiecheng(oneTimes+twoTimes)/(jiecheng(oneTimes)*jiecheng(twoTimes));
        return res;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloor (int number) {
        // write code here
        // 由于青蛙只能 跳一格 或者 跳两格
        // 可以得知 n 为偶数时，青蛙最多跳 n 步 ，每步一格 ， 最少跳 n/2 步 每步两格
        // 每次添加青蛙跳两格的次数，并且进行排列组合即可拿到所有的可能性
        int oneStep , twoStep;
        oneStep = number;
        twoStep = 0;

        int res = 0;
        while(oneStep>=0){
            res += checkSolusion(oneStep,twoStep);
            oneStep -= 2;
            twoStep += 1;
        }
        System.out.println(jiecheng(5));

        return res;
    }
}

发表于 2025-06-18 21:28:42 回复(0)

Java

clever-kalamh7o

定义dp结果数组，下标即为台阶数，对应的数组值即为跳跃方案。

import java.util.*;


public class Solution {
    public int jumpFloor (int number) {
        // write code here
        if (number == 1) return 1;
        else if (number == 2) return 2;
        else {
            int[] dp = new int[number+1];
            dp[1] = 1;
            dp[2] = 2;

            for (int i = 3; i <= number; i++) {
                dp[i] = dp[i-1] + dp[i-2];
            }

            return dp[number];
        }
    }
}

如果将其看成一种“斐波那契数列”的变形，即：当前台阶的跳法=前一个台阶跳法＋前两个台阶跳法。与斐波那契数列仅仅是初值情况不同。

import java.util.*;


public class Solution {
    public int jumpFloor (int number) {
        // write code here
        if (number == 1) return 1;
        else if (number == 2) return 2;
        else {
            int oneFloor = 1;
            int twoFloor = 2;

            for (int i = 3; i <= number; i++) {
                twoFloor += oneFloor;
                oneFloor = twoFloor - oneFloor;
            }

            return twoFloor;
        }
    }
}

发表于 2025-02-26 14:01:59 回复(0)

Java

有力量的小白要双休

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param number int整型
     * @return int整型
     */
    public int jumpFloor (int number) {
        // 如果n小于等于1，直接输出结果1
        if (number <= 1) {
            return 1;
        }
        // 初始化数组，长度为n+1
        int[] dp = new int[number + 1];
        dp[0] = 1;
        dp[1] = 1;
        // 从第2级台阶开始计算
        for (int i = 2; i <= number; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[number];
    }
}

发表于 2024-10-17 21:55:22 回复(0)

Java

人间水长东

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloor (int number) {
        // write code here
        // 算法核心思想：递归回溯

        return process(number);
    }

    public int process(int n) {
        // 递归出口
        if (n == 1) {
            // 如果只有1阶台阶，则只有1种跳法
            return 1;
        }
        if (n == 2) {
            // 如果有2阶台阶，则有2种跳法
            return 2;
        }

        // 分支搜索
        // 其余任意情况，可拆解成两大类情况
        // 从n-2阶跳2阶 + 从n-1阶跳1阶
        return process(n - 2) + process(n - 1);
    }
}

发表于 2024-09-17 00:22:14 回复(0)

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int jumpFloor (int number) {
        int dp1 = 1, dp2 = 1;
        for (int i = 2; i <= number; i++) {
            dp1 = dp2 + dp1;
            dp2 = dp1 - dp2;
        }
        return dp1;
    }
}

发表于 2024-08-04 14:24:24 回复(0)

Java

JavaSouth南哥

import java.util.*;

public class Solution {
    public int jumpFloor (int number) {
        if (number == 1) return 1;
        else if (number == 2) return 2;
        else {
            return jumpFloor(number - 1) + jumpFloor(number - 2);
        }   
    }
}

发表于 2024-01-07 13:18:57 回复(0)

Java

Yg0802.

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    int[] dp = new int[40];
    public int jumpFloor(int num) {
        if (dp[num] != 0) {
            return dp[num];
        }
        if (num == 1 || num == 2) {
            dp[num] = num;
            return dp[num];
        } else {
            int count = jumpFloor(num - 1) + jumpFloor(num - 2);
            dp[num] = count;
            return dp[num];
        }
    }
}

编辑于 2023-12-08 16:54:08 回复(0)

Java

butt

 public int jumpFloor (int number) {
        // write code here
        if(number<2)
        return 1;
        //当n=2时，return得到1+1=2
        else
            return jumpFloor(number-2)+(jumpFloor(number-1));
    }

发表于 2023-09-04 22:06:30 回复(0)

Java

这个算法非得学吗

到达第n个台阶的方法只有两种要不是从第n-1个跳一步，要不是从n-2跳两步，递归到第三个台阶。。。。。

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param number int整型

* @return int整型

public int jumpFloor (int number) {

// write code here

if(number == 1) return 1;

if(number == 2) return 2;

return jumpFloor(number - 1)+jumpFloor(number - 2);

}

发表于 2023-08-20 21:51:58 回复(0)

Java

做则必成的勇气和信心

public int jumpFloor (int number) {
        int[] dp=new int[number+1];//如果不初始化dp[0]，那就存数组的时候从1开始
        if(number==1){  //如果数组下标从1开始，那么这里1的情况就要单独加进去
            return 1;
        }
        dp[1]=1;//到第一个台阶
        dp[2]=2;//到第二个台阶
        for(int i=3;i<number+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];
    }

发表于 2023-07-11 17:06:30 回复(1)

Java

牛客552672642号

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloor (int number) {
        return jumpFloor_(0, 1, number);
    }

    private int jumpFloor_(int acc1, int acc2, int number) {
        return number == 0
                ? acc2
                : jumpFloor_(acc2, acc1 + acc2, number - 1);
    }
}

发表于 2023-06-18 19:07:51 回复(0)

Java

Zhima1234

public class Solution {
    public int jumpFloor(int target) {
        if (target == 0 || target == 1) {
            return 1;
        }
        // 跳到i级台阶有多少种跳法
        int[] dp = new int[target + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            // 第i级可以从前两级跳过来，也可以从前一级跳过来
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}

发表于 2023-05-31 08:49:52 回复(0)

Java

牛客-68643578743367

public class Solution {
    public int jumpFloor(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

发表于 2023-04-04 16:59:45 回复(0)

Java

牛客979698536号

public class Prac01 { public static void main(String [] args){ // 一只青蛙一次可以跳上1级台阶，也可以跳上2级。  // 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 // 输入： //        2 // // 返回值： //        2 // // 说明： // 青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2  Scanner scanner = new Scanner(System.in);  int n1 = scanner.nextInt();  if(n1==1){
            System.out.println("1");  }if(n1==2){
            System.out.println("2");  }if(n1==3){ // 111 21 12  n1为3 3位到2位  System.out.println("3");  }if(n1==4){// 1111 211 121 112 22 由4位到3位到2位  System.out.println("5");  }
        
    }
}