👆关注“博文视点Broadview”，获取文末赠书 ---- 递归 递归算法是一类非常常用的算法，它是一种直接或间接调用原算法本身的算法。递归算法最大的特点就是“自己调用自己”，对于一些具有递归特性的问题，使用递归算法来解决会更加简单明了，且易于实现。 在使用递归算法解决实际的问题时，要自顶向下地将一个大问题拆分成同类的小问题，然后利用同类问题这一特性构造出解决问题的递归函数，也就是这种“自己调用自己”的模型，再通过程序实现这个递归函数。 下面通过一个实例理解递归算法。 走楼梯问题：一个楼梯共有10级台
本文作者：ivweb 程柳锋 当Javascript的性能遇到瓶颈，或者需要增强Javascript能力的时候，就需要依赖native模块来实现了。 应用场景 日常工作中，我们经常需要将原生的N
看一个十一假期发生的小例子，带你走进递归。十一放假时去火车站排队取票，取票排了好多人，这个时候总有一些说时间来不及要插队取票的小伙伴，我已经排的很遥远了，发现自己离取票口越来越远了呢，我超级想知道我现在排在了第几位(前提:前面不再有人插队取票了)，用递归思想我们应该怎么做？
本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中，所推送的面试题目及编程练习的一次汇总，期间还包括三次直播课的分享，均由腾讯导师给大家讲解，该系列博文的发布已得到 IMWeb 前端学院助教的许可
大家好，很高兴又和你们见面啦！在上一篇的内容中，我们把汉诺塔问题从头到尾剖析了一遍，我自己在剖析的过程中，对这个问题的理解也得到了提升，不知道朋友们你们在看完上一篇的内容有什么感受，今天我们来解决第二个经典问题——青蛙跳台阶问题。
1.青蛙先跳一级台阶，接下来他就会还有3级台阶要去跳，而这3级台阶不就是上面3级台阶的重复吗！所以此时一共有3种跳法
跳上两级台阶，青蛙可以一级一级跳，跳两次0-->1-->2，也可以直接跳到二级台阶,跳一次，0--->2；总共2种方法。
经过上面的分析，我们知道了一级、二级和三级台阶的跳法，现在要我们求 n 级台阶的跳法，我们可以这样思考：
“递归”在生活中的一个典例就是“问路”。如图小哥哥进入电影院后找不到自己的座位，问身边的小姐姐“这是第几排”，小姐姐也不清楚便依次向前询问，问至第一排的观众后依次向后反馈结果，“我是第一排”，“我是第二排”，···，最终确定自己座位所在排数。
题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法？
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
根据题意，我们可以看出整个题目的思路是十分清晰的。我们需要想办法将题目语言，先转化为数学符号，最后再转化为编程语言就十分方便了。下面我们来分析一些这道题目。
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
“降维打击”之所以给人如此之震撼，在于它以极简的方式，从更高的、全新的技术视角有效解决了当前困局。
https://github.com/Coxhuang/Python-DataStructure
面试题9：斐波那契数列及其变形(跳台阶、矩形覆盖) 提交网址： http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tp
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入： 输入可能包含多个测试样例，对于每个测试案例， 输入包括一个整数n(1<=n<=50)。 输出： 对应每个测试案例， 输出该青蛙跳上一个n级的台阶总共有多少种跳法。 样例输入： 6 样例输出： 32 解题思路： 这道题目跟之前的跳台阶大同小异，只是跳台阶的阶数从1变到了n,也就是说，不再是跳一下或者跳两下的问题，而是跳n下的问题。那么解题的思路显然还得逆向分析，我们发现：
大家好，我是年年！今天的内容是关于一道算法题——青蛙跳台阶。这是一个面试很喜欢考的题，看到它，大部分人脑海中应该立马出现：斐波那契亚数列——递归——f(n)=f(n-1)+f(n-2)。
青蛙跳台阶问题是一个经典的递归问题，可以使用递归方法来解决。 问题描述：有n级台阶，青蛙每次可以跳1级台阶或者2级台阶，问青蛙跳上n级台阶有多少种不同的跳法。 解决方法：
ps:最近几天正在刷一些有关动态规划的题，我会把自己学习时的想法以及做题的想法记录下来。（小白第一次写作，希望大家多多支持）
题目： 一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级，求总共有多少总跳法，并分析算法的时间复杂度。 注： 这道题最近经常出现，包括Microsoft 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。 思路一： 首先我们考虑最简单的情况：如果只有1 级台阶，那显然只有一种跳法，如果有2 级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1 级；另外一种就是一次跳2 级。 现在我们再来讨论一般情况：我们把n 级台阶时的跳法看成是n 的函数，记为f(n)。当n>2 时，第一次跳的时
因为要求的是第n个泰波那契序列，所以我们可以创建一个长度为 n 的dp表，用来表示第i位置的泰波那契序列（即：dp[i]表示：第 i 个泰波那契序列的值）。
题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。 斐波那契（Fibonacci）数列定义如下： 效率很低的解法： long long Fibonacci_Solution1
用n个硬币搭台阶，要求第k级台阶必须有k个硬币。问n个硬币最多能够搭多少级台阶？ 如五个硬币最多能够搭两级台阶，8个硬币最多搭三级台阶。
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
LeetCode题目源地址：https://leetcode-cn.com/problems/climbing-stairs/
思路解析 这一题与上述的那一题大同小异，只要注意一些小问题，显然该题的状态转换方程也和上题差不多，但是这题，有一个不同的地方就是，他不仅可以跳一步，两步，他还能跳三步，甚至是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。 源代码
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 难易程度：easy
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入： 输入可能包含多个测试样例，对于每个测试案例， 输入包括一个整数n(1<=n<=70)。 输出： 对应每个测试案例， 输出该青蛙跳上一个n级的台阶总共有多少种跳法。 样例输入： 5 样例输出： 8 题目分析： 这道题很明显正向分析是不行的，也就是说，最后面的一个台阶，要依赖于前面台阶的。所以，最后一个台阶的方法数目可以由前面计算出来。那么，仔细想一下，一个青蛙只能跳1-2步，也就是说，最后一个台阶肯
推演得到公式：dp[i] = dp[i-1] + dp[i-2] 你还可以使用动态规划来解题呀，具体思路如下：
You are climbing a stair case. It takes n steps to reach to the top.
本篇开始将介绍与算法和数据操作相关的面试题。有很多算法都可以用「递归」和「循环」两种不同的方式实现。通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。面试时我们需要根据题目的特点和面试官的需求灵活选择。
一只青蛙一次可以跳上 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级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
斐波那契数列的应用 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法 ''' 前提： 青蛙一次只能跳1级或2级台阶 n f(m) 假设第1次跳1级台阶 f(n-1) 假设第1次跳2级台阶 f(n-2) f(n) = f(n-1) + f(n-2) f(1) = 1 f(2) = 2 ''' def jumpFloor(number): res = [1, 2] while len(res) <= number: res.app
这样出现的问题主要是在递归的过程中会出现很多重复的计算，比如我们每次计算第n个的时候，都需要重新计算前面的n-1和n-2，这样每个值其实都会被计算两遍。简单的处理是：从下往上开始算，从第0个一直算到第n个。 代码如下：
我们刷leetcode的时候，经常会遇到动态规划类型题目。动态规划问题非常非常经典，也很有技巧性，一般大厂都非常喜欢问。今天跟大家一起来学习动态规划的套路，文章如果有不正确的地方，欢迎大家指出哈，感谢感谢~
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
