我要招人

去企业版

首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题

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

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围： $1 \le n \le 20$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(1)$

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

牛客题解官

发表于 2020-05-29 14:56:47

精华题解题目的主要信息：对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数 n为正整数，求青蛙跳上n级台阶的方案数举一反三：学习完本题的思路你可以解决如下题目： JZ69. 跳台阶 JZ10. 斐波那契数列 JZ70. 矩形覆盖方法一：动态规划（推荐使用）知识点：动态规划动态规划算法展开全文

漫漫云天自翱翔

发表于 2021-07-01 16:19:41

精华题解题解一：递归题解思路：考虑最后一步是跳几阶到达目标位置的。主要分析： 1.令f(n)表示n阶台阶总的跳法 2.假设最后只跳一步，那么f(n) = f(n-1); 最后跳两步，那么f(n) = f(n-2)；以展开全文

未来0116

发表于 2021-06-23 19:29:55

精华题解一.题目描述JZ9 跳台阶扩展问题题目链接:https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/ta/coding-interv 展开全文

把牛妹带回家

发表于 2019-07-26 15:45:30

易知 f(n)=f(n-1)+f(n-2)+……f(1)f(n-1)=f(n-2)+……f(1)两式相减得f(n)=2f(n-1) # -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, number): # 展开全文

中工升达预备毕业生

发表于 2019-08-29 16:05:20

f(n)=f(n-1)+f(n-2)+...+f(1)f(n-1)=f(n-2)+...f(1)得:f(n)=2*f(n-1) public class Solution { public int JumpFloorII(int target) { return 1<& 展开全文

Cyril-廖思睿

发表于 2020-01-03 21:21:42

数学问题，一行代码即可易知 f(n)=f(n-1)+f(n-2)+……f(1) f(n-1)=f(n-2)+……f(1)两式相减得 f(n)=2f(n-1)而 f(1) = 1所以 f(n) = pow(2, n - 1)由此得出： public class Solution { publ 展开全文

那就来一个吧

发表于 2019-09-29 19:30:28

变态跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析设级台阶有种跳法，根据最后一次跳台阶的数目可以分解为最后一次一级，则前面需要跳级，有种跳法；最后一次跳两级，则前面需要跳级，有种跳法。以此类推易知，$$两式展开全文

jalr4ever

发表于 2019-08-05 22:36:20

迭代本质上是斐波那契数列的变种，普通跳台阶是一步与两步，问题规模缩小到分成最后要跳到第 n 阶可以跳两次或者一次去求解，所以，在普通跳台阶，设置两个临时变量存下跳一次或者两次时，前面会有多少种可能的结果 dp 就是可以由什么状态推导出最后的状态，斐波那契数列是由前两种状态，而这里就是由前 n - 展开全文

心谭

发表于 2019-12-29 23:47:36

【JavaScript题解】【剑指offer】【变态跳台阶】题目描述一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。专注前端与算法的系列干货分享，欢迎关注(¬‿¬)：「微信公众号：心谭博客」| xxoo521.co 展开全文

郭家兴0624

发表于 2019-08-10 10:00:21

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析：所有情况的和可以分解为第一次跳0个台阶，剩余n个台阶的跳法+第一次跳1个台阶，剩余n-1个台阶的跳法+第一次跳2个台阶，剩余n-2个台阶的跳法+...+第一次跳n-1个台阶展开全文