8.跳台阶-剑指offer-Python2.7

75 阅读 0 评论 50 点赞

我是靠谱客的博主暴躁鼠标，这篇文章主要介绍8.跳台阶-剑指offer-Python2.7，现在分享给大家，希望可以做个参考。

剑指offer第8题牛客网在线编程链接 https://www.nowcoder.com/activity/oj
跳台阶

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

思路：这是一个没有第一项（0）的斐波那契数列
n=1,一种跳法；n=2,一次跳一个，跳两次，或者一次跳两个跳一次，共有两种跳法。当n>2时，n个台阶，设有f(n)种跳法，如果第一次选择跳一个台阶，剩下的n-1个台阶有f(n-1)种跳法；如果第一次选择跳两个台阶，剩下的n-2个台阶有f(n-2)种跳法。所以当有n个台阶时，有f(n)=f(n-1)+f(n-2)种跳法。所以，其实这是一个没有第一项（0）的斐波那契数列。

Python2.7编写

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        f,g = 1,2
        if number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            for i in range(3, number+1):
                f,g = g, f + g
        return g

参考：斐波那契数列解法 https://blog.csdn.net/Jason43/article/details/83895901