面试题之走楼梯问题

题目:

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

相关文章

来自专栏java一日一条

一个基于Java的开源URL嗅探器

今天,我们很高兴做一个分享,因为我所在的 Linkedin 公司 开源了我们做的一个ULR探测工具:URL-Detector Java 库。

482
来自专栏SDNLAB

OpenDaylight VTN源码及架构分析

VTN是opendaylight中负责租户隔离的工程,最近对源码和架构研究了一段时间,现将总结如下。 从VTN架构图我们可以看出,VTN共分为两个模块:VTN ...

3355
来自专栏机器之心

代码优化指南:人生苦短,我用Python

选自pythonfiles 机器之心编译 参与:Panda 前段时间,Python Files 博客发布了几篇主题为「Hunting Performance i...

31213
来自专栏北京马哥教育

LaTeXila:Linux 的多语言 LaTeX 编辑器简介

豌豆贴心提醒,本文阅读时间7分钟 LaTeXila 是一个多语言 LaTeX 编辑器,专为那些偏爱 GTK+ 外观的 Linux 用户设计。这个软件除了操作简...

3329
来自专栏张善友的专栏

live messenger与稀疏文件—Sparse File Bit

今天进行磁盘整理,发现一个奇怪的文件SimilarityTable_1:下面是我的C盘整理后的结果 卷   (C:)     卷的大小             ...

1785
来自专栏Python中文社区

pyecharts(一):Python可视化利器

專 欄 ❈陈键冬,Python中文社区专栏作者 GitHub: https://github.com/chenjiandongx ❈ pyecharts 是一...

3555
来自专栏施炯的IoT开发专栏

用本地代码实现屏幕方向自适应的Windows Mobile程序

    在Windows Mobile平台的应用程序开发过程中,如何处理屏幕方向改变对程序带来的影响是一个重要的问题。Allen Lee的文章《WM有约(四):...

2057
来自专栏二次元

各种语言按钮事件特征码

比如:弹提示框,就下MessageBoxA,注册表的,就下RegOpenKeyA等等

830
来自专栏腾讯云实验室

腾讯云实验室的正确投稿姿势

腾讯云实验室上线了在线投稿能力,现在除了官方推出的实验室之外,允许有能力的开发者把自己的技术和经验通过在实验室投稿的方式来进行分享和传播。

3962
来自专栏Python中文社区

Django 博客教程(三):创建应用和编写数据库模型

專 欄 ❈追梦人物,Python中文社区专栏作者。电子科技大学计算机学院研究生,从事大数据分析研究方向。主要使用 Python 语言进行相关数据的分析,熟练使...

1839

扫码关注云+社区