面试题之走楼梯问题

题目:

一个台阶总共有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 条评论
登录 后参与评论

相关文章

来自专栏专知

【论文推荐】最新十二篇情感分析相关论文—自然语言推理框架、网络事件、多任务学习、实时情感变化检测、多因素分析、深度语境词表示

26060
来自专栏木子昭的博客

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

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

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

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

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

45390
来自专栏CVer

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

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

51630
来自专栏专知

【干货】Python大数据处理库PySpark实战——使用PySpark处理文本多分类问题

【导读】近日,多伦多数据科学家Susan Li发表一篇博文,讲解利用PySpark处理文本多分类问题的详情。我们知道,Apache Spark在处理实时数据方面...

13.1K100
来自专栏专知

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

35530
来自专栏大数据挖掘DT机器学习

机器学习&数据挖掘知识点大总结

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

442140
来自专栏CVPy

OpenCV玩九宫格数独(三):九宫格生成与数独求解

在此之前两篇文章中分别介绍了如何从九宫格图片中提取出已知数字和如何用knn训练数字识别模型。在这些前期工作都已经完成的基础上,接下来我们需要做什么呢?这篇文章将...

1K00
来自专栏DHUtoBUAA

正六边形网格化(Hexagonal Grids)原理与实现

 在路径规划、游戏设计栅格法应用中,正六边形网格不如矩形网格直接和常见,但是正六边形具有自身的应用特点,更适用于一些特殊场景中,比如旷阔的海洋、区域或者太空。...

53250
来自专栏专知

【论文推荐】最新5篇行人再识别(ReID)相关论文—迁移学习、特征集成、重排序、 多通道金字塔、深层生成模型

【导读】专知内容组整理了最近五篇行人再识别(Person Re-identification)相关文章,为大家进行介绍,欢迎查看! 1.Unsupervised...

54970

扫码关注云+社区

领取腾讯云代金券