首页 > 试题广场 >

跳台阶

[编程题]跳台阶

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

有力量的小白要双休

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");  }
        
    }
}

发表于 2023-04-03 20:20:48 回复(0)

Java

Hadoopdoop

public class Solution {
    public int jumpFloor(int target) {
       return jump(target);
    }

    private int jump(int target) {
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        return jump(target - 1) + jump(target-2);
    }
}

发表于 2023-03-10 15:45:19 回复(0)

Java

贾天龙

public class Solution {
    public int jumpFloor(int target) {
        // 辅助数组：用于存储计算结果，避免重复运算
        int []data = new int[target];

        return jumpFloor(target, data);
    }


    public int jumpFloor(int target,  int[] data) {
        // 递归结束条件1：两阶台阶：2种跳法，一阶台阶：1种跳法
        if (target <= 2) {
            return target;
        }
        // 递归结束条件2：在数组中查找计算过的结果，如果有，则不用计算，节省时间
        if (data[target - 1] != 0) {
            return data[target - 1];
        }
        // 将结果进行保存，避免重复计算
        data[target - 1]  = jumpFloor(target - 1, data) + jumpFloor(target - 2, data);

        return data[target - 1];
    }
}

发表于 2023-03-06 17:06:15 回复(0)

Java

键盘都敲坏了.

public class Solution {

    /** 一、自顶向下
    public int jumpFloor(int target) {
       if(target < 0){
            return 0;
        }else if(target== 1){
            return 1;
        }else if(target == 2){
            return 2;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    } */

    /** 二、自底向上  */
   public int jumpFloor(int target) {
       return jumpFloor(0, target);
    }
    /**
     * 递归求解
     * @param n 当前跳了几层台阶
     * @param target 总共有多少层
     * @return 返回有多少种跳法
     */
    public int jumpFloor(int n, int target) {
        if(n > target) return 0; // 如果当前跳的台阶 大于 实际有的台阶，返回跳法0种

        if(target - n == 1) return 1; // 如果当前跳的台阶 与 实际有的台阶，相差1 返回跳法1种
        else if(target - n == 2) return 2; // 如果当前跳的台阶 与 实际有的台阶，相差2 返回跳法2种

        int i = jumpFloor(n + 1, target);   // 当前这一位置跳一层
       int i2 = jumpFloor(n + 2, target); // 当前这一位置跳两层
        return i + i2; // 两种跳法相加
       //return jumpFloor(n + 1, target) + jumpFloor(n + 2, target);      
     }
}

编辑于 2022-11-22 19:05:45 回复(2)

Java

小杨yyy

public class Solution {
    public int count=0;
    public int jumpFloor(int target) {
        if(target==0){
            return 0;
        }
        backWard(target,0);
        return count;
    }
    //回溯算法
    public void backWard(int n,int step){
        //如果step刚好累加到等于n，则count++
        if(step==n){
            count++;
            return;
        }
        //优先向上走一步
        if(step+1<=n){
            backWard(n,step+1);
        }
        //其次一步的走完后，再尝试走两不
        if(step+2<=n){
            backWard(n,step+2);
        }
    }

}

发表于 2022-11-14 12:10:18 回复(0)

Java

景午

斐波那契通项公式接题，O(1)时间复杂度

public class Solution {
    public int jumpFloor(int target) {
        return (int) Math.round((Math.pow((1 + Math.sqrt(5)) / 2, target + 1) - Math.pow((1 - Math.sqrt(5)) / 2, target + 1)) / Math.sqrt(5));
    }
}

发表于 2022-11-10 00:19:57 回复(1)