009. 斐波那契数列

Description

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

Solutions

当然，教科书上最标准的做法其实是比较低效的：

# -*- 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)

直接用累加的方式：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 0:
            return 0
        if n == 1:
            return 1
        f1 = 0
        f2 = 1
        fn = 0
        for i in range(2, n + 1):
            fn = f1 + f2
            f1 = f2
            f2 = fn
        return fn

问题延伸

青蛙跳台阶

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

这个就是初始值不一样而已，具体分析时利用递归思路来考虑就可以了。跳到下一层台阶的方式有两种，一是从当前台阶跳一步上去，二是从当前台阶的下一个台阶一步跳两层上去，这就是有点儿像斐波那契数的例子了，只是当我们在平底时初始值为1.

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 1:
            return 1
        f1 = 1
        f2 = 1
        fn = 0
        
        for i in range(2, number + 1):
            fn = f1 + f2
            f2 = f1
            f1 = fn
        return fn

变态版青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这个看起来复杂实则是最简单的了，通过 f(n) 和 f(n-1) 的等式相减，就可以得到递归式，一下就写出来代码了：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <= 1:
            return 1
        return 2 * self.jumpFloorII(number-1)

矩阵覆盖

我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        f1 = 2
        f2 = 1
        fn = 0
        for i in range(3, number+1):
            fn = f1 + f2
            f2 = f1
            f1 = fn
        return fn

References

009. 斐波那契数列