面试题之走楼梯问题

题目:

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

相关文章

来自专栏专知

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

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

4264
来自专栏大数据文摘

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

1977
来自专栏专知

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

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

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

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

33512
来自专栏专知

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

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

3994
来自专栏专知

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

2012
来自专栏专知

【论文推荐】最新六篇行人再识别相关论文—特定视角、多目标、双注意匹配网络、联合属性-身份、迁移学习、多通道金字塔型

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

7275
来自专栏CVer

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

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

2663
来自专栏专知

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

1983
来自专栏CVer

[计算机视觉论文速递] 2018-03-11

通知:这篇推文有10篇论文速递信息,涉及目标检测、行人重识别Re-ID、图像检索和Zero-Shot Learning等方向 这篇文章本来是在2018-03-1...

4018

扫码关注云+社区