原标题：剑指Offer（八）：跳台阶

原文来自：CSDN      原文链接：https://blog.csdn.net/baidu_31657889/article/details/99681281

一、引子

这个系列是我在牛客网上刷《剑指Offer》的刷题笔记，旨在提升下自己的算法能力。
查看完整的剑指Offer算法题解析请点击：剑指Offer完整习题解析

二、题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

1、思路

首先我可以确切的告诉你，这种简单的跳台阶也是一个斐波那契数列，不信你自己从简单的数1，2，3…自己推论一下。

首先我们考虑最简单的情况。如果只有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)。分析到这里，我们不难看出这实际上就是斐波那契数列了。

解法和上一节的实现基本一样。使用循环，n=1是输出1，n=2是输出2，剩下的以此类推。

2、编程实现

python2.7

代码实现方法：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 1:
            return 1
        a = 1
        b = 1
        for i in range(1,number):
            a , b = b,a+b
        return b

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com