面试题之走楼梯问题

题目:

一个台阶总共有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专栏

用 Python 分析 YouTube 百万条数据

1372
来自专栏猿人谷

跳台阶问题

题目: 给定一个有N个台阶的楼梯,一个人从下到上开始跳台阶,这个人有两种跳的方式:一次跳一个台阶,一次跳两个台阶; 问:从台阶底端跳到台阶顶端,有多少种跳台阶的...

1649
来自专栏数据结构与算法

BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp)

  小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有 多少种染色方案,Sun很快就给出了答案.进一步...

693
来自专栏数据结构与算法

到天宫做客(2017寒假培训测试压轴题)

题目描述 有一天,我做了个梦,梦见我很荣幸的接到了猪八戒的邀请,到天宫陪他吃酒。我犹豫了。天上一日,人间一年啊!当然,我是个闲人,一年之中也没有多少时日是必须在...

3376
来自专栏牛客网

快手后台开发面经

2774
来自专栏编程

Python学习笔记1——斐波那契数列

这是一个高中同学问我的问题,本来是用C来写的,正好正在学Python,就用Python重写了一遍当作练习。 下面是题目要求: ? ? 一道很简单的题目,但有些细...

19010
来自专栏郭耀华‘s Blog

leetcode第一天

leetcode 第一天 2017年12月24日 第一次刷leetcode真的是好慢啊,三道题用了三个小时,而且都是简单题。 数组 1.(674)Longe...

33811
来自专栏C语言及其他语言

[每日一题]斐波那契数列

问题 1131: 【C语言训练】斐波纳契数列 题目描述 斐波纳契数列 1,1,2,3,5,8,13,21,34,55,89……这个数列则称为“斐波纳契数列”...

26410
来自专栏杨熹的专栏

机器学习算法应用中常用技巧-1

参考:Udacity ML纳米学位 1. 取样 数据量很大的时候,想要先选取少量数据来观察一下细节。 indices = [100,200,300] # 把s...

3087
来自专栏专知

关关的刷题日记10——Leetcode 1. Two Sum 方法1

关小刷刷题10 – Leetcode 1. Two Sum 方法1 题目 Given an array of integers, return indices ...

2749

扫描关注云+社区