首页 > 试题广场 >

跳台阶

[编程题]跳台阶
  • 热度指数：1099479 时间限制：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
牛客562978599号头像 牛客562978599号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param number int整型
 * @return int整型
 */
 /*动态规划，递归进行步伐深度探索，当抵达预先设定的台阶级数时（每次递归都对参数进行加法，额度为循环参数），对跳法加一,退出当前循环时，还需要将此循环所加的步数减去，最终返回跳法最大数量*/

int dp(int number,int *floor_num,int *num_jump_kind)
{

    if(*floor_num == number)
    {
        *num_jump_kind += 1;
        return 0;
    }
    else if(*floor_num > number || *floor_num < 0)
    {
        return 0;
    }

    for(int i = 1 ; i < 3 ; i ++)
    {
        int step = 0 ;
        step += i;
        *floor_num += step;
        dp(number,floor_num,num_jump_kind);
        *floor_num -= step;
    }
    return 0;
}

int jumpFloor(int number ) {
    // write code here
    int floor_num = 0;
    int num_jump_kind = 0;
    dp(number,&floor_num,&num_jump_kind);
    return num_jump_kind;
}
发表于 2025-11-09 18:41:46 回复(1)
C
牛客337395198号头像 牛客337395198号
请教一下大佬们，为什么我这段代码在我的IDE上能正常运行，在这个网站编译不通过
#include <stdio.h>
/*就是递归，看一眼就懂了*/

int main() {
    int number,ans;
    scanf("%d",&number);
    ans=jumpFloor(number);
    printf("%d",ans);
    return 0;
}

int jumpFloor(int number ) {
    if(number==1) return 1;
    else if(number==2) return 2;
    else return jumpFloor(number-1)+jumpFloor(number-2);// write code here
}

发表于 2025-01-02 17:54:03 回复(0)
C
cs小白_头像 cs小白_ 
#include <stdlib.h>
int jumpFloor(int number ) {
    // write code here
    int* a=(int*)malloc(sizeof(int)*(number+1));
    a[1]=1,a[2]=2;
    for (int i=3; i<=number; i++) {
          a[i]=a[i-1]+a[i-2];
    }
    return a[number];
}

发表于 2024-11-29 16:23:22 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int jumpFloor(int number ) {
    if(number==1)
        return 1;
    else if(number==2)
        return 2;
    return jumpFloor(number-2)+jumpFloor(number-1);
}

发表于 2024-03-23 22:15:38 回复(0)
C
牛客470596767号头像 牛客470596767号
#include <stdio.h>
#include <string.h>
int jiecheng(int n,int m)
{
    if(m-1<0)
    return 1;
    else
    return n*jiecheng(n-1,m-1);
}
int count(int n,int m)
{
    if(n-m<1)
    return 1;
    else
    return jiecheng(n,m)/jiecheng(m,m)+count(n-1,m+1);
}

int main()
{
    int n=0;
    int ret=0;
    scanf("%d",&n);
    while(n<=0&&n>40)
    {
        printf("输入有错,请重新输入n:");
        scanf("%d",&n);
    }
    ret=count(n-1,1);
    printf("这就是小青蛙选择跳台阶的方法:%d\n",ret);
    return 0;
发表于 2024-02-27 23:09:46 回复(1)
C
关山gs头像 关山gs
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param number int整型
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    int n;
    if(number==1) n=1;
    else if(number==2) n=2;
    else{
        n=jumpFloor(number-1)+jumpFloor(number-2);
    }
    return n;
}
发表于 2023-11-14 18:24:16 回复(0)
C
唱跳Rap打篮球的_______头像 唱跳Rap打篮球的_______ 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    int a[number];
    a[0]=1;
    a[1]=2;
    for(int i=2;i<number;i++){
        a[i]=*(a+i-1)+*(a+i-2);
    }
    return *(a+number-1);
for循环代码
发表于 2023-10-06 14:06:03 回复(0)
C
80后大叔头像 80后大叔

动态规划最经典的基础题

int jumpFloor(int number ) {
    // write code here
    int dp[40] = {0};
    dp[0] =1;
    dp[1] =2;
    for(int i=2; i<number; i++) {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[number-1];
}
发表于 2022-11-12 11:25:08 回复(0)
C
牛客340146020号头像 牛客340146020号
经典斐波拉契数列，我还画图画半天研究，气死…… 
/**
 * 
 * @param number int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int jumpFloor(int number ) {
    // write code here
    if(number==1||number==2)
        return number;
    return jumpFloor(number-1)+jumpFloor(number-2);
}

发表于 2022-06-29 11:53:25 回复(0)
C
✨LAUGH头像 ✨LAUGH 
/**
 * 
 * @param number int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int jumpFloor(int number ) {
    // write code here
    if(number==1)
        return 1;
    if(number==2)
        return 2;
    return jumpFloor(number-1)+jumpFloor(number-2);
}

发表于 2022-05-01 12:18:40 回复(0)
C
Chromium丶头像 Chromium丶
C
int jumpFloor(int n) {
    int a[n+1];
    a[1] = 1,a[2] = 2;
    for(int i = 3;i<=n;i++) a[i] = a[i-1] + a[i-2];
    return a[n];
    // write code here
}

发表于 2022-03-16 22:59:19 回复(0)
C
牛客296365098号头像 牛客296365098号
相同的代码，C通过，python超时
发表于 2022-03-02 17:37:52 回复(0)
C
CreatorSY头像 CreatorSY 
static int g_num = 0;

static void cal_cycle(int number) {
    if (number <= 1) {
        g_num++;
        return;
    }
    cal_cycle(number - 1);
    cal_cycle(number - 2);
}

int jumpFloor(int number) {
    g_num = 0;

    cal_cycle(number);

    return g_num;
}
发表于 2021-12-31 18:35:11 回复(0)
C
xiaolock883头像 xiaolock883
解题思路：
通过观察题意，第一个台阶只有一种走法，第二个台阶只有两种走法。并且如果想要走到第x个台阶，可能是在x-1个台阶直接走一步，或者是在x-2台阶直接走两步来实现的。因此第x个台阶的走法是第x-1个台阶走法加上第x-2个台阶的走法。可以考虑利用递归，从上往下算，直到算到2，最后return number；
由于时间复杂度为o(n)，因此不能通过以下代码实现 
int jumpFloor(int number ) {
    // write code here
    if(number <= 2)
    {
        return number;
    }
    else
        return jumpFloor(number-1)+jumpFloor(number-2);
}
因为如果使用上述代码，则是从number往下展开，每次再调用number减一和number减二的jumpFloor的值。每使用一次jumpFloor函数便需要将比他小的全部数字都算出来，于是计算整体后将有大量重复计算的值。
于是考虑从下往上计算，将计算出来的值存入数组中，先算出arr[0] arr[1] arr[2] 的值，再利用循环，将arr[3],arr[4]....arr[n]的值算出来，最后进行返回arr[number]
代码如下 
int jumpFloor(int number ) {
    // write code here
    int arr[41];
    int i = 0;
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    for(i = 1;i<=number;i++)
    {
        arr[i+2] = arr[i] + arr[i+1];
    }
    return arr[number];
}

发表于 2021-12-01 16:11:39 回复(0)
C
叶藏于林头像 叶藏于林
经典Fibonacci 
int jumpFloor(int number) {
    // write code here
    if (number <= 2) {
        return number;
    }
    return jumpFloor(number-1) + jumpFloor(number-2);
}


发表于 2021-10-27 15:40:54 回复(0)
C
大白饭的白饭头像 大白饭的白饭
/**
 *
 * @param number int整型
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    if(number<=0)
    {
return 0;
    }
    else if(number<2)
    {
        return 1;
     }
    else if(number<3)
    {
        return 2;
    }
    else
    {
     return jumpFloor(number-1)+jumpFloor(number-2);   
    }
}
发表于 2021-10-18 20:31:40 回复(0)
C
海饼干666头像 海饼干666
/**
 *
 * @param number int整型
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    if(1 == number) return 1;
    else if(2 == number) return 2;
   
    return jumpFloor(number-1)+jumpFloor(number-2);
   
}
发表于 2021-08-18 14:47:06 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

跳台阶

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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