我要招人

去企业版

首页 > 试题广场 >

跳台阶

[编程题]跳台阶

热度指数：1082292 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围： $1 \leq n \leq 40$

要求：时间复杂度： $O(n)$ ，空间复杂度： $O(1)$

示例1

输入

输出

说明

青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入

输出

算法知识视频讲解

牛客题解官

发表于 2020-05-29 14:53:44

精华题解 #描述此题和斐波拉契数列做法一样。也将用三个方法来解决，从入门到会做。考察知识：递归，记忆化搜索，动态规划和动态规划的空间优化。难度：一星 #题解 ###方法一：递归题目分析，假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n- 展开全文

漫漫云天自翱翔

发表于 2021-06-22 22:48:14

精华题解题解一:记忆化搜索假设有n阶台阶，在所有的跳法中，由于青蛙一次只能跳1步或者2步，所以青蛙跳上最后一阶只能由f(n-1)+1 或者f(n-2)+2 这两种情况得来。即：f(n)=f(n-1)+f(n-2)同理:f(n-1)=f(n-2)+f(n-3),以此类推。这其实就是一个斐波拉契数列。图示如下：展开全文

牛客题解官

发表于 2022-04-22 12:36:01

精华题解题目主要信息：一只青蛙一次可以跳1阶或2阶求跳到第nnn阶的种类数举一反三：学习完本题的思路你可以解决如下题目： BM62.斐波那契数列 BM64.最小花费爬楼梯 BM69.把数字翻译成字符串方法一：迭代相加（推荐使用）知识点：动态规划动态规划算法的基本思想是：将待求解的问题分解成展开全文

未来0116

发表于 2021-06-18 13:16:46

精华题解一.题目描述有n级台阶，青蛙每一次可以跳上去1级台阶或者2级台阶，问有多少种跳法？二.算法1(利用数组求)我们可以通过推理来找出。第3位可以由第1阶台阶跳2阶或第2阶段跳1阶段得出。第4位可以由第2阶台阶跳2阶或第3阶段跳1阶段得出。第5位可以由第3阶台阶跳2阶或第4阶段跳1阶段得出。......最展开全文

牛客313925129号

发表于 2021-07-16 15:16:27

精华题解对于第n个台阶，要么从第n-1个台阶一步跨过来，要么从第n-2个台阶一步跨过来（从第n-2个台阶先走一个台阶再走一个台阶的情况，包含在了从第n-1个台阶走一个台阶的情况中了）。所以说有f(n)=f(n-1)+f(n-2)，边界值为f(1)=1，f(2)=2。此时，跳台阶问题可以完全转化为斐波那契数列展开全文

Veggie

发表于 2020-02-27 23:02:54

题目来源：牛客网-剑指Offer专题题目地址：跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。题目解析这是一道经典的递推题目，你可以想如果青蛙当前在第n级台阶上，那它上一步是在哪里呢？显然，由于它可以跳1 展开全文

jalr4ever

发表于 2019-08-05 21:40:40

迭代本质上还是斐波那契数列，所以迭代也可以求当成 dp 问题来想的话：首先分析问题，它最终解是由前面的解累积起来的解，如何缩小问题的规模？首先可知，第一阶有只能一步，一种；，第二阶可以两次一步、一次两步两种若楼梯阶级 n = 3 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种展开全文

̯͡↗Captain⚡

发表于 2019-08-19 21:43:47

思路：跳n级台阶相当于n-1和n-2级台阶的和原因：n级台阶就相当于n-1级再跳一次一阶的和n-2级再跳一次2阶的语言：javascript： function jumpFloor(number) { //这里写的越高递归的时候调用栈就越小，但是越多的话，多写的那部分效果就越打折扣。好比是消除展开全文

Oh~Sunny

发表于 2020-01-02 20:41:15

解释：我们把n级台阶时的跳法看成n的函数，记为f(n)。当n>=2时，第一次跳的时候有两种不同的选择：第一次跳1级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1); 第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同展开全文

数据结构和算法

发表于 2021-03-21 12:36:03

1，递归的写法这题我们可以参照之前分析的青蛙跳台阶问题，其实原理是完全一样的我们来分析一下：当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1 当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2 当n等于3的时候，他可以从一级台阶上跳两步上来，也展开全文

不是江小白

发表于 2021-08-02 21:01:35

1. 解题思路之暴力分析法由于题目要求一次只能跳 1个台阶或 2个台阶，所以我们可以暴力画出青蛙🐸从1阶到5阶的跳法来寻找规律，下面看图：青蛙遇到1个台阶的时候，只有一种跳法：青蛙遇到2个台阶的时候，有两种跳法：青蛙遇到3个台阶的时候，有三种跳法：青蛙遇到 4个台阶的时候，有五种展开全文

4thirteen2one

发表于 2022-07-23 14:42:43

感觉这道题相比NC65 斐波那契数列，更适合拿来当作动态规划的入门训练题，因为相比 Fibonacci 数列已经给好了递推公式，这道题需要自己从实际问题中抽象出问题模型，虽然最终抽象出来还是 Fibonacci 数列哈。下面是过程分析。已知：爬到第 1 阶，只可能也只用爬 1 阶就能完成，共展开全文