#描述
此题和斐波拉契数列做法一样。也将用三个方法来解决，从入门到会做。
考察知识：递归，记忆化搜索，动态规划和动态规划的空间优化。
难度：一星
#题解
###方法一：递归
题目分析，假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-
展开全文
题解一:记忆化搜索假设有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),以此类推。这其实就是一个斐波拉契数列。图示如下：
展开全文
题目主要信息：
一只青蛙一次可以跳1阶或2阶
求跳到第nnn阶的种类数
举一反三：
学习完本题的思路你可以解决如下题目：
BM62.斐波那契数列
BM64.最小花费爬楼梯
BM69.把数字翻译成字符串
方法一：迭代相加（推荐使用）
知识点：动态规划
动态规划算法的基本思想是：将待求解的问题分解成
展开全文
一.题目描述有n级台阶，青蛙每一次可以跳上去1级台阶或者2级台阶，问有多少种跳法？二.算法1(利用数组求)我们可以通过推理来找出。第3位可以由第1阶台阶跳2阶或第2阶段跳1阶段得出。第4位可以由第2阶台阶跳2阶或第3阶段跳1阶段得出。第5位可以由第3阶台阶跳2阶或第4阶段跳1阶段得出。......最
展开全文
对于第n个台阶，要么从第n-1个台阶一步跨过来，要么从第n-2个台阶一步跨过来（从第n-2个台阶先走一个台阶再走一个台阶的情况，包含在了从第n-1个台阶走一个台阶的情况中了）。所以说有f(n)=f(n-1)+f(n-2)，边界值为f(1)=1，f(2)=2。此时，跳台阶问题可以完全转化为斐波那契数列
展开全文
题目来源：牛客网-剑指Offer专题题目地址：跳台阶 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 题目解析 这是一道经典的递推题目，你可以想如果青蛙当前在第n级台阶上，那它上一步是在哪里呢？ 显然，由于它可以跳1
展开全文
迭代 本质上还是斐波那契数列，所以迭代也可以求 当成 dp 问题来想的话：首先分析问题，它最终解是由前面的解累积起来的解，如何缩小问题的规模？ 首先可知，第一阶有只能一步，一种；，第二阶可以两次一步、一次两步两种 若楼梯阶级 n = 3 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种
展开全文
思路：跳n级台阶相当于n-1和n-2级台阶的和原因：n级台阶就相当于n-1级再跳一次一阶的和n-2级再跳一次2阶的 语言：javascript： function jumpFloor(number)
{
//这里写的越高递归的时候调用栈就越小，但是越多的话，多写的那部分效果就越打折扣。好比是消除
展开全文
解释：我们把n级台阶时的跳法看成n的函数，记为f(n)。当n>=2时，第一次跳的时候有两种不同的选择： 第一次跳1级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1); 第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同
展开全文
1，递归的写法
这题我们可以参照之前分析的青蛙跳台阶问题，其实原理是完全一样的
我们来分析一下：
当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1
当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2
当n等于3的时候，他可以从一级台阶上跳两步上来，
展开全文
1. 解题思路之暴力分析法 由于题目要求一次只能跳 1个台阶或 2个台阶，所以我们可以暴力画出青蛙🐸从1阶到5阶的跳法来寻找规律，下面看图： 青蛙遇到1个台阶的时候，只有一种跳法： 青蛙遇到2个台阶的时候，有两种跳法： 青蛙遇到3个台阶的时候，有三种跳法： 青蛙遇到 4个台阶的时候，有五种
展开全文
感觉这道题相比NC65 斐波那契数列，更适合拿来当作动态规划的入门训练题，因为相比 Fibonacci 数列已经给好了递推公式，这道题需要自己从实际问题中抽象出问题模型，虽然最终抽象出来还是 Fibonacci 数列哈。
下面是过程分析。
已知：
爬到第 1 阶，只可能也只用爬 1 阶就能完成，共
展开全文
另一种形式的斐波那契 public class Solution { public int JumpFloor(int target) { if (target==1 || target==0){
展开全文
不用递归的写法，因为递归会有大量重复计算。
function jumpFloor(number)
{
const results = [];
results[1] = 1;
results[2] = 2;
if(number>2){
for(va
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
