【转】http://zhedahht.blog.163.com/blog/static/25411174200731844235261/
题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
分析:这道题最近经常出现,包括MicroStrategy等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。
首先我们考虑最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳的方法了:一种是分两次跳,每次跳1级;另外一种就是一次跳2级。
现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另外一种选择是第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。
我们把上面的分析用一个公式总结如下:
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
分析到这里,相信很多人都能看出这就是我们熟悉的Fibonacci序列。至于怎么求这个序列的第n项,请参考本面试题系列第16题,这里就不在赘述了。
分享到:
相关推荐
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法? 若把条件修改成一次可以跳一级,也可以跳2级...也可以跳上n级呢?
青蛙跳台阶问题(斐波那契数列变形)一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。示例 1:输入:n = 2 输出:2示例 2:输入:n = 7 输出
面试题10- II. 青蛙跳台阶问题题目链接面试题10- II. 青蛙跳台阶问题题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。示例 1:输入:n =
跳台阶、变态跳台阶、矩形覆盖其实都和斐波那契数列是一类问题,文中通过示例代码介绍的非常详细,下面话不多说了,来一起看看详细的介绍吧。 跳台阶 问题描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该...
题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少种跳法,并分析算法的时间复杂度。答:用一个函数f(n)来表示n级台阶总的跳法。1、只有1个台阶,则f(1) = 1;2、有2个台阶,则f(2) = 2;3、当...
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。链接:
跳台阶问题 题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级。 求总共有多少总跳法,并分析算法的时间复杂度。 分析: 也是比较基础的题目,通过递归可以方便的求解 代码实现如下(GCC编译通过):...
定义dp[i]表示跳上一个i级台阶的跳法数,则dp[0] = dp[1] = 1,对于任意i(i >=2),跳上i级台阶可以通过跳1级或者跳2级到达,所以dp
题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。示例 1:输入:n = 2输出:2示例 2:输入:n = 7输出:21解析1:本质是DP,对DP进行了拆
主要介绍了使用C++求解跳台阶问题的方法,通过递归算法来解决,不算难,文中给出了计算思路,需要的朋友可以参考下
变色弹球跳台阶HTML5源码
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:2 ...
html5实现经典的变色弹珠跳台阶游戏源码 html5实现经典的变色弹珠跳台阶游戏源码
HTML5变色弹球跳台阶小游戏,点击台阶可变换红,黄,紫等颜色台阶。
jQuery变色弹珠跳台阶小游戏代码是一款点击台阶变换红黄紫颜色台阶,弹珠跳跃过关。
青蛙上台阶所有解 兔子繁殖问题 斐波那契数列