剑指offer 面试题10- I. 斐波那契数列（易）& LeetCode 509. 斐波那契数（易）

经典的斐波拉契数列问题，在递归求解的基础上，还由什么可以优化的地方？

Tag

动态规划

本题考点

考查应聘者对递归、循环的理解及编码能力。 考查应聘者对时间复杂度的分析能力。 如果面试官采用的是青蛙跳台阶的问题，那么同时还在考查应聘者的数学建模能力。

题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1： 

1
2
输入：n = 2
输出：1
示例 2： 
1
2
输入：n = 5
输出：5
提示：0 <= n <= 100

测试用例设计： 功能测试（如输入3、5、10等）。 边界值测试（如输入0、1、2）。 性能测试（输入较大的数字，如40、50、100等）

直觉

1、递归

时间复杂度为以 \(n\) 的指数方式递增的指数级别 \(O(2^n)\)
空间复杂度为常数级别 \(O(1)\)

2、动态规划（循环迭代）

时间复杂度为线性级别 \(O(n)\)
空间复杂度为常数级别 \(O(1)\)

3、矩阵乘法解斐波拉契数列

令 U 为单位矩阵，F为基础矩阵，则： \[ U = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}\ F = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \]

则 \(F^1\)：

\[ F^1 = \begin{bmatrix} f(2) & f(1) \\ f(1) & f(0) \\ \end{bmatrix} = F * U = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \]

且利用数学归纳法可知：

\[ F^n = \begin{bmatrix} f(n+1) & f(n) \\ f(n) & f(n-1) \\ \end{bmatrix} = F^{n-1} * U = \begin{bmatrix} f(n) & f(n-1) \\ f(n-1) & f(n-2) \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \]

可得如下通式矩阵： \[ F^n = \left[ \begin{matrix} f(n+1) &f(n)\\ f(n) &f(n-1) \end{matrix} \right] = \left[ \begin{matrix} 1 &1\\ 1 &0 \end{matrix} \right] ^ {n} \] 通式矩阵里面的 \(f(n)\) 就是斐波那契数列的第 \(n\) 项，所以求出 \[\left[ \begin{matrix} 1 &1\\ 1 &0 \end{matrix} \right]\] 的 \(n-1\) 次方，取对应位置 \((0, 1)\) 上的 \(f(n)\) 就可以了。可知，只需求得矩阵 \[\left[ \begin{matrix} 1 &1\\ 1 &0 \end{matrix} \right] ^ {n}\] 即可得到 \(f(n)\)，现在将问题转化为如何求矩阵 \[\left[ \begin{matrix} 1 &1\\ 1 &0 \end{matrix} \right]\] 的乘法。可以考虑如下性质： \[ a^n =\left\{ \begin{aligned} a^{n/2} \times a^{n/2} & , & n \% 2 == 0 \\ a^{(n-1)/2} \times a^{(n-1)/2} \times a & , & n \% 2 != 0 \end{aligned} \right. \] 从上面的公式中我们可以看出，我们想求得 \(a\) 的 \(n\) 次方，就要先求得 \(a\) 的 \(n/2\) 次方，再把 \(n/2\) 次方的结果平方一下即可。这可以用递归的思路实现。这种基于递归用 \(O(logN)\)的时间求得 \(N\) 次方的算法值得我们重视。

时间复杂度为对数级别 \(O(logN)\)
空间复杂度为常数级别 \(O(1)\)

从方法1到方法3，算法时间复杂度依次降低。

参考链接

求解斐波那契第n项的几种解法(含矩阵乘法+快速幂) Python实现

代码

1、递归

1
2
3
4
5
6
7
8
9
class Solution:
    def fib(self, n: int) -> int:
        """递归解法
        :param n: int
        :return: int 
        """
        MODULUS = 1000000007
        if n < 2: return n
        return (self.fib(n-1) + self.fib(n-2)) % MODULUS

2、动态规划（循环迭代）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import unittest

class Solution:
    def fib(self, n: int) -> int:
        """典型的动态规划问题 状态转移方程为 F(N) = F(N-1) + F(N-2)
        :param n: int
        :return: int 
        """
        MODULUS = 1000000007
        # res = [0, 1]  # 面试时不要用数组，空间复杂度为O(n)。
        head = 1  # 用三个单独数字解决，空间复杂度为O(1)。
        pre_head = 0
        res = 0
        if n < 2: return n
        for _ in range(2, n+1):
            res = head + pre_head
            pre_head = head
            head = res
        return res % MODULUS


class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [0, 2, 5]
        answers = [0, 1, 5]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.fib(inputs[i]))
        self.assertEqual(res, answers)

    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

3、矩阵乘法解斐波拉契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import unittest

class Solution:
    def fib(self, n: int) -> int:
        MODULUS = 1000000007
        if n <= 1: return max(n, 0)
        res = [[1, 0], [0, 1]]  # 单位矩阵，等价于1
        A = [[1, 1], [1, 0]]  # A矩阵
        while n:
            if n & 1: res = self.mul(res, A)  # 如果n是奇数，或者直到n=1停止条件
            A = self.mul(A, A)  # 快速幂
            n >>= 1  # 整除2，向下取整
        return res[0][1]  % MODULUS  # 最后返回的是矩阵右上角那个值 也就是 f(n)

    def mul(self, a, b):  # 首先定义二阶矩阵乘法运算
        c = [[0, 0], [0, 0]]  # 定义一个空的二阶矩阵，存储结果
        for i in range(2):  # row
            for j in range(2):  # col
                for k in range(2):  # 新二阶矩阵的值计算
                    c[i][j] += a[i][k] * b[k][j]
        return c


class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [0, 2, 5]
        answers = [0, 1, 5]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.fib(inputs[i]))
        self.assertEqual(res, answers)

    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

举一反三

面试题10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1： 

1
2
输入：n = 2
输出：2
示例 2： 
1
2
输入：n = 7
输出：21
提示：0 <= n <= 100 本题和LeetCode 70. 爬楼梯（易）一模一样，考察的是建模能力，面试者能不能把具体问题抽象从数学模型？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import unittest

class Solution:
    def numWays(self, n: int) -> int:
        """动态规划问题：状态转移方程为 f(n) = f(n-1) + f(n-2)
        """
        if n <= 2:  return 2 if n==2 else 1
        MODULUS = 1000000007
        pre_stage = 1  # 跳到第1级的方法只有1种
        prior_stage = 2  # 跳到第2级有2种方法，要么从第一级跳一下到这一级，要么从平地跳两下到这一级。
        res = 0
        for _ in range(3, n+1):
            res = pre_stage + prior_stage
            pre_stage = prior_stage
            prior_stage = res
        return res % MODULUS

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [0, 1, 2, 3, 4, 5, 6, 7]
        answers = [1, 1, 2, 3, 5, 8, 13, 21]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.numWays(inputs[i]))
        self.assertEqual(res, answers)

    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

改进版青蛙跳台阶问题

在青蛙跳台阶的问题中，如果把条件改成：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？我们用数学归纳法可以证明 \(f(n)=2^{n-1}\)。

矩形块占位问题

我们可以用2×1（图2.12的左边）的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2×1的小矩形无重叠地覆盖一个2×8的大矩形（图2.12的右边），总共有多少种方法？

Snipaste_2020-04-28_11-00-48.png

图2.12一个2×1的矩形和2×8的矩形我们先把2×8的覆盖方法记为 \(f(8)\)。用第一个2×1的小矩形去覆盖大矩形的最左边时有两种选择：竖着放或者横着放。当竖着放的时候，右边还剩下2×7的区域，这种情形下的覆盖方法记为\(f(7)\)。接下来考虑横着放的情况。当2×1的小矩形横着放在左上角的时候，左下角必须和横着放一个2×1的小矩形，而在右边还剩下2×6的区域，这种情形下的覆盖方法记为\(f(6)\)，因此\(f(8)=f(7)+f(6)\)。此时我们可以看出，这仍然是斐波那契数列。

关于循环和递归的时间复杂度

递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解递归实现的效率不如循环。

另外，递归中有可能很多计算都是重复的，从而对性能带来很大的负面影响。递归的本质是把一个问题分解成两个或者多个小问题。如果多个小问题存在相互重叠的部分，就存在重复的计算。在面试题10“斐波那契数列”及面试题60“n个骰子的点数”中，详细地分析递归和循环的性能区别。

通常应用动态规划解决问题时我们都是用递归的思路分析问题，但由于递归分解的子问题中存在大量的重复，因此我们总是用自下而上的循环来实现代码。这样一来就不用重复求解重叠子问题，我们将在面试题14“剪绳子”、面试题47“礼物的最大价值”及面试题48“最长不含重复字符的子字符串”中详细讨论如何用递归分析问题并基于循环写代码。

除效率之外，递归还有可能引起更严重的问题：调用栈溢出。在前面的分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。在上述例子中，如果输入的参数比较小，如10，则它们都能返回结果55。但如果输入的参数很大，如5000，那么递归代码在运行的时候就会出错，但运行循环的代码能得到正确的结果12502500。