剑指 Offer 2022/7/2

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(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：
输入：n = 2
输出：1

示例 2：
输入：n = 5
输出：5

代码思路

1. 递归
2. 动态规划

class Solution:
    def fib(self, n: int) -> int:
        dp=[0]*(n+2)
        dp[1]=1
        for i in range(2,n+1):dp[i]=(dp[i-1]+dp[i-2])%1000000007
        return dp[n]
1
2
3
4
5
6

3. 矩阵快速幂
   方法一的时间复杂度是 O(n)。使用矩阵快速幂的方法可以降低时间复杂度。
   首先我们可以构建这样一个递推关系：
   [ 1 1 1 0 ] [ F ( n ) F ( n − 1 ) ] = [ F ( n ) + F ( n − 1 ) F ( n ) ] = [ F ( n + 1 ) F ( n ) ] \left[
   1110$$\begin{array}{cc}1& 1\\ 1& 0\end{array}$$
   \right] \left[
   F(n)F(n−1)$$\begin{array}{c}F(n)\\ F(n-1)\end{array}$$
   \right] = \left[
   F(n)+F(n−1)F(n)$$\begin{array}{c}F(n)+F(n-1)\\ F(n)\end{array}$$
   \right] = \left[
   F(n+1)F(n)$$\begin{array}{c}F(n+1)\\ F(n)\end{array}$$
   \right] [11​10​][F(n)F(n−1)​]=[F(n)+F(n−1)F(n)​]=[F(n+1)F(n)​]
   因此：
   [ F ( n + 1 ) F ( n ) ] = [ 1 1 1 0 ] n [ F ( 1 ) F ( 0 ) ] \left[
   F(n+1)F(n)$$\begin{array}{c}F(n+1)\\ F(n)\end{array}$$
   \right] = \left[
   1110$$\begin{array}{cc}1& 1\\ 1& 0\end{array}$$
   \right] ^n \left[
   F(1)F(0)$$\begin{array}{c}F(1)\\ F(0)\end{array}$$
   \right] [F(n+1)F(n)​]=[11​10​]n[F(1)F(0)​]
   令：
   M = [ 1 1 1 0 ] M = \left[
   1110$$\begin{array}{cc}1& 1\\ 1& 0\end{array}$$
   \right] M=[11​10​]
   因此只要我们能快速计算矩阵 M的 n 次幂，就可以得到F(n) 的值。如果直接求取 $M^n$
   ，时间复杂度是 O(n)，可以定义矩阵乘法，然后用快速幂算法来加速这里 $M^n$
   的求取。
   计算过程中，答案需要取模 $1\text{e}9+7$。

class Solution:
    def fib(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n < 2:
            return n

        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            c = [[0, 0], [0, 0]]
            for i in range(2):
                for j in range(2):
                    c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD
            return c

        def matrix_pow(a: List[List[int]], n: int) -> List[List[int]]:
            ret = [[1, 0], [0, 1]]
            while n > 0:
                if n & 1:
                    ret = multiply(ret, a)
                n >>= 1
                a = multiply(a, a)
            return ret

        res = matrix_pow([[1, 1], [1, 0]], n - 1)
        return res[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

剑指 Offer 10- II. 青蛙跳台阶问题

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

示例 1：
输入：n = 2
输出：2

示例 2：
输入：n = 7
输出：21

示例 3：
输入：n = 0
输出：1

代码思路

1. 动态规划
   和斐波那契数列一样

class Solution:
    def numWays(self, n: int) -> int:
        dp=[1]*(n+1)
        for i in range(2,n+1):
            dp[i]=(dp[i-1]+dp[i-2])%1000000007
        return dp[n]
1
2
3
4
5
6

2. 矩阵快速幂