面试题之走楼梯问题

题目:

一个台阶总共有n 级,如果一次可以跳1 级,也可以跳2 级,求总共有多少总跳法,并分析算法的时间复杂度。

注: 这道题最近经常出现,包括Microsoft 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。

思路一:

首先我们考虑最简单的情况:如果只有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(n-2)。 我们把上面的分析用一个公式总结如下: / 1 (n=1) f(n) = 2 (n=2) \ f(n-1) + (f-2) (n>2) 分析到这里,相信很多人都能看出这就是我们熟悉的Fibonacci 序列。(O(n))

///非递归方法 
int Fibonacci1(unsigned int N)  
{  
 if(N<=2)  
 return N;  
 int fibtwo=2;  
 int fibone=1;  
 int fibN=0;  
 for(unsigned int i=3;i<=N;i++)  
    {  
        fibN=fibone+fibtwo;  
        fibone=fibtwo;  
        fibtwo=fibN;  
    }  
 return fibN;  
}  

拓展: 如果能走3个台阶呢?又该如何做?

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【学习】常用的机器学习&数据挖掘知识点

Basis(基础): MSE(Mean Square Error 均方误差),LMS(LeastMean Square 最小均方),LSM(Least Squa...

35012
来自专栏木子昭的博客

K近邻(knn)算法预测电影类型案例1案例2 Facebook入住地点

K近邻思想: 根据你的"邻居们"来确定你的类别 你一觉醒来,不知道自己身在何方里,你能通过计算机定位到周围5个"最近的"邻居,其中有4个身处火星,1个身处月...

3715
来自专栏CVer

谷歌CVPR 2018最全总结:45篇论文,Ian Goodfellow GAN演讲PPT下载

谷歌在今年的CVPR上表现强势,有超过200名谷歌员工将在大会上展示论文或被邀请演讲,45篇论文被接收。在计算机视觉领域,生成对抗网络GAN无疑是最受关注的主题...

3543
来自专栏专知

【论文推荐】最新七篇行人再识别相关论文—多级高斯模型、密度自适应、注意力感知组成网络、图像-图像域适应、自适应采样

2222
来自专栏专知

【论文推荐】最新六篇视频分类相关论文—教师学生网络、表观-关系、Charades-Ego、视觉数据合成、图蒸馏、细粒度视频分类

【导读】专知内容组为大家推出最新六篇视频分类(Video Classification)相关论文,欢迎查看!

1173
来自专栏大数据文摘

如何优雅地测量一只猫的体积

2087
来自专栏专知

【论文推荐】最新5篇语音识别(ASR)相关论文—音频对抗样本、对抗性语音识别系统、声学模型、序列到序列、口语可理解性矫正

【导读】专知内容组整理了最近五篇语音识别(Automatic Speech Recognition, ASR)相关文章,为大家进行介绍,欢迎查看! 1. Aud...

5084
来自专栏专知

【论文推荐】最新5篇知识图谱相关论文—强化学习、习知识图谱的表示、词义消除歧义、并行翻译嵌入、图数据库

【导读】专知内容组整理了最近五篇知识图谱(Knowledge Graph)相关文章,为大家进行介绍,欢迎查看! 1. DeepPath: A Reinforce...

4174
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

关于Cewu Lu等的《Combining Sketch and Tone for Pencil Drawing Production》一文铅笔画算法的理解和笔录。

相关论文的链接:Combining Sketch and Tone for Pencil Drawing Production        第一次看《Com...

3609
来自专栏专知

【论文推荐】最新七篇图像检索相关论文—草图、Tie-Aware、场景图解析、叠加跨注意力机制、深度哈希、人群估计

2483

扫码关注云+社区