斐波那契数列(同跳台阶)

题目

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。n<=39

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

解题思路

递归解法

但是运行效率低，且有运算重复的地方，容易导致递归栈溢出

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.Fibonacci(n-1) + self.Fibonacci(n-2)

循环方式实现

class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0:
            return 0
        if n == 1:
            return 1
        first = 0
        second = 1
        result = 0
        for i in range(n):
            result = first + second
            first = second
            second = result
        return first
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 0:
            raise Exception("ERR")
        if number == 1:
            return 1
        if number == 2:
            return 2
        a = 1
        b = 1
        result = 0
        for i in range(number):
            a, b = b, a+b
        return a