大家好,很高兴又和你们见面啦!在上一篇的内容中,我们把汉诺塔问题从头到尾剖析了一遍,我自己在剖析的过程中,对这个问题的理解也得到了提升,不知道朋友们你们在看完上一篇的内容有什么感受,今天我们来解决第二个经典问题——青蛙跳台阶问题。
题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
题目: 给定一个有N个台阶的楼梯,一个人从下到上开始跳台阶,这个人有两种跳的方式:一次跳一个台阶,一次跳两个台阶; 问:从台阶底端跳到台阶顶端,有多少种跳台阶的方式? 分析: 首先我们考虑最简单的情况。如果只有1个台阶,那么显然只有一种跳法;如果 是2级台阶,那么有2种跳法。对于一个有n级台阶的楼梯来说,我们设跳法为 f(n) ,假如我们先跳1个台阶,则剩下有 n-1 个台阶,跳法为 f(n-1) 次,假如我们先跳2个台阶,则剩下 n-2 阶,跳法为 f(n-2);由此可以推出,对于一个n阶的楼梯,有以下这
该题目为跳台阶题目的延伸,普通跳台阶每次跳的阶数(1或2),而该题目每次跳的阶数进化为(1~N),其实万变不离其宗,看下图:
题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对于每个测试案例, 输入包括一个整数n(1<=n<=50)。 输出: 对应每个测试案例, 输出该青蛙跳上一个n级的台阶总共有多少种跳法。 样例输入: 6 样例输出: 32 解题思路: 这道题目跟之前的跳台阶大同小异,只是跳台阶的阶数从1变到了n,也就是说,不再是跳一下或者跳两下的问题,而是跳n下的问题。那么解题的思路显然还得逆向分析,我们发现:
同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree 剑指 Offer(C++版本)系列:总目录和一些提高效率的说明 剑指 Offer(
思路解析 这一题与上述的那一题大同小异,只要注意一些小问题,显然该题的状态转换方程也和上题差不多,但是这题,有一个不同的地方就是,他不仅可以跳一步,两步,他还能跳三步,甚至是N步,所以,显然N阶的方案里面肯定也包括了在跳N-3阶的基础上再跳3阶的方案。一次类推,所以显然 dp[i]=dp[i-1]+dp[i-2]+…+dp[1],你以为这样就结束了吗?NONONO,不要忘记了,他还能跳N阶,所以状态方程应该是dp[i]=dp[i-1]+dp[i-2]+…+dp[0]+1。 源代码
但是实际上汉诺塔问题解决方案都是最优解,我们不走弯路,我们的目的性非常强,我们最终目的都是移动到c,所以我们可以先让顶端的木块直接到c
题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件.
原题链接 描述 一个楼梯共有 n 级台阶,每次可以走一级或者两级,问从第 0 级台阶走到第 n 级台阶一共有多少种方案。
今天来给大家分享一下关于青蛙跳台阶拓展问题我自己的思路,由于这个时候我还是初学C语言,所以我自己的思路一开始没有那么清晰,所以大家仅供参考.
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
根据题意,我们可以看出整个题目的思路是十分清晰的。我们需要想办法将题目语言,先转化为数学符号,最后再转化为编程语言就十分方便了。下面我们来分析一些这道题目。
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:
这样出现的问题主要是在递归的过程中会出现很多重复的计算,比如我们每次计算第n个的时候,都需要重新计算前面的n-1和n-2,这样每个值其实都会被计算两遍。简单的处理是:从下往上开始算,从第0个一直算到第n个。 代码如下:
本篇开始将介绍与算法和数据操作相关的面试题。有很多算法都可以用「递归」和「循环」两种不同的方式实现。通常基于递归的实现方法代码会比较简洁,但性能不如基于循环的实现方法。面试时我们需要根据题目的特点和面试官的需求灵活选择。
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
1、hashMap的2倍扩容机制为什么是2倍 2、在java8和java7中,hashMap的hash函数有什么不同 3、100个数字排序怎么做?100万个数字排序怎么做? 4、设计模式你了解哪些?说一说 5、valitile关键字你知道吗? 6、synchrolzie关键字和Lock的区别你知道吗?为什么Lock的性能好一些? 7、线程池的几种实现你知道吗? 8、ArrayList和LinkedList你知道吗?你知道它怎么动态扩容的吗? 9、数据库的事务你知道吗?acid特性; 10、Mysql中事务的
《剑指offer》专题—算法训练day03 接着上一篇我们提到的 斐波那契数列,我们来 简单了解一下 动态规划问题 现阶段我们解决动归问题,只需要了解三个步骤 1.定义状态 2.编写状态转
本期题目:猴子跳台阶 🐒🏞️ 题目 一天一只顽猴想要从山脚爬到山顶, 途中经过一个有n个台阶的阶梯, 但是这个猴子有个习惯,每一次只跳🐵1步或🐒3步 试问?猴子通过这个阶梯有多少种不同的跳跃方式 输入 输入只有一个数n, 0 < n < 50 代表此阶梯有多个台阶 输出描述 有多少种跳跃方式 题解地址 📤 ⭐️ 华为 OD 机考 Python https://blog.csdn.net/hihell/article/details/129004798 ⭐️ 华为 OD 机考 C++ https://blog
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
1、题目: 现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0).n<=39。
牛客网 NC68 跳台阶 描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 递归实现: public class Solution { public int jumpFloor(int target) { if(target == 1 || target == 2){ return target; } return jumpF
面试题9:斐波那契数列及其变形(跳台阶、矩形覆盖) 提交网址: http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tp
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
假设还有n阶要跳,那么这一次有n种跳法 1 2 3...n,而且当我们跳i个台阶后则下次有n-i个台阶可以跳...直到跳到最后一阶整个跳台阶结束,算一种方法 这里的sum则统计了所有的结果
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
程序调用自生的编程技巧称作递归。所谓递归就必然存在着递出与回归,递归的全过程其实是将一个问题分成若干个解法相同的问题,将初始的数据一直往后传送,当到达一个临届值后开始回归,从原路返回实现问题的解决。 递归策略使得只需要少量的程序就可以描述出解题中多次重复的计算,大大减少了代码的长度。 递归的精髓就在于大事化小。
一个楼梯共有 n 级台阶,每次可以走一级或者两级,问从第 0 级台阶走到第n 级台阶一共有多少种方案。
青蛙跳台阶问题是一个经典的递归问题,可以使用递归方法来解决。 问题描述:有n级台阶,青蛙每次可以跳1级台阶或者2级台阶,问青蛙跳上n级台阶有多少种不同的跳法。 解决方法:
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法?
问题分析:假设 为跳台阶的总跳法,当 时, ;当 时, ;当 时,如果先跳1级台阶,有 种方法,如果先跳2级台阶,有 种方法,依次类推,可以得到下面的递推公式:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
昨天的题解 题目 每天一道剑指offer-牛客网跳台阶 来源:牛客网对应专题 题目详述 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 题目详解 思路 是剑指offer思路,每次使用两个变量a,b来计算下一个数的值sum,然后a,b,sum分别是斐波那契数列中的三个数,那么就令a=b,b=sum,这样a和b就往下移动了一个位置,再计算sum就是滴4个数了,重复这个过程即可。 代码 public class Solution {
https://github.com/Coxhuang/Python-DataStructure
摘要:递归是一种应用非常广泛的算法(或者编程技巧)。之后我们要讲的很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以,搞懂递归非常重要,否则,后面复杂一些的数据结构和算法学起来就会比较吃力
在数学中,递归是将一个未知项逐渐拆分为小项来计算出未知项的值。那么根据这种数学思想,递归程序的思路应该是:
新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里 P1425 小鱼的游泳时间:点击这里 顺序与分支 P1422 小玉家的电费:点击这里 P1085 不高兴的津津:点击这里 P1089 津津的储蓄计划:点击这里
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
问题分析:假设f(n)f(n)f\left ( n \right )为跳台阶的总跳法,当n=1n=1n=1时,f(n)=1f(n)=1f\left ( n \right )=1;当n=2n=2n=2时,f(n)=2f(n)=2f\left ( n \right )=2;当n=3n=3n=3时,如果先跳1级台阶,有f(n−1)=f(2)f(n−1)=f(2)f\left ( n-1 \right )=f\left ( 2 \right )种方法,如果先跳2级台阶,有f(n−2)=f(1)f(n−2)=f(1)f\left ( n-2 \right )=f\left ( 1 \right )种方法,依次类推,可以得到下面的递推公式:
1.青蛙先跳一级台阶,接下来他就会还有3级台阶要去跳,而这3级台阶不就是上面3级台阶的重复吗!所以此时一共有3种跳法
题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。 斐波那契(Fibonacci)数列定义如下: 效率很低的解法: long long Fibonacci_Solution1
9.算法题:跳台阶高级,每次可以跳任意步,问跳上n阶台阶有几种方法,关键f(n)=2f(n-1),对应牛客剑指OfferJZ9 跳台阶扩展问题
领取专属 10元无门槛券
手把手带您无忧上云