《剑指offer》 10.斐波那契数列和青蛙跳台阶

剑指offer
留言

note: 虽然本科的时候讲递归必讲斐波那契，但是不意味着递归最适合于斐波那契，因为存在很多重复计算，且递归也需要额外空间。

还有关于求余的问题，有三个公式需要记一下

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

1
2
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

方法一：递归（容易超时）

思路

简单思维，照搬公式。

需要思考的是哪里复杂了呢？原因是产生了很多重复计算，如下图所示

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int fib(int n) {
        if(n<2){
            return n;
        }
        
        return (fib(n-1)+fib(n-2))%1000000007;
    }
};

复杂度分析

方法二：递归优化，减少重复计算

原理

将计算后的值放入数组进行存储，需要时不用再递归计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    int store[101] = {0};
public:
    int fib(int n) {
        if(n<2){
            return n;
        }
        if(store[n]!=0)
            return store[n];
        store[n] = (fib(n-1)+fib(n-2))%1000000007;
        return store[n];
    }
};

复杂度分析

  • 时间复杂度：$O(n)$。因为我们进行了存储，所以我们减少了叶子节点的数量，每个元素只需要计算一次，所以为线性复杂度
  • 空间复杂度：$O(n)$。显然我们除了递归的空间外，还需要存储所有叶子的空间。空间开销变大了。

方法三： 动态规划（也有人说是尾递归）

原理

将斐波那契数列的性质$f(n+1) = f(n)+f(n-1)$为转移方程。定义一个一维数组$dp$，$dp[i]$表示斐波那契数列的第$i$个数字。

  • 状态方程：$dp[i] = dp[i-1]+dp[i-2]$
  • 初始状态: $dp[0]=0,dp[1]=1$
  • 返回值：$dp[n]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int store[101] = {0};
public:
    int fib(int n) {
        if(n<2)
            return n;
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i] = (dp[i-1]+dp[i-2])%1000000007; 
        }
        return dp[n];
    }
};

复杂度分析

  • 时间复杂度$O(n)$。每个值计算一次
  • 空间复杂度$O(n)$。需要一个数组存放计算的值。

方法四：动态规划+滚动数组（进一步减少空间，最常用）

原理

事实上分析方法三中的数组，我们发现其实没必要存储所有中间计算过程中的值，因为我们只用得到$n-1$和$n-2$这两个中间值。

所以我们可以使用两个变量来存储，就可以将数组省略掉，这其实是一种滚动数组的思想

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int store[101] = {0};
public:
    int fib(int n) {
        int a=0,b=1,sum=0;
        for(int i=0;i<n;i++){
           	sum = (a+b)%1000000007;
           	a = b;
			b = sum;
        }

        return a;
    }
};

复杂度分析

  • 时间复杂度$O(n)$。每个值计算一次
  • 空间复杂度$O(1)$。只使用了常数级别的额外空间。

方法五：矩阵快速幂（不常用）

原理

注意： 本题中这种方法不可用，因为会发生溢出错误（n太大了）

进一步降低时间复杂度的方法。

建立一个递推关系如下所示

因此我们有:

如果令

因此如果我们可以快速计算矩阵M的$n$次幂，就可以得到$F(n)$的值。如果直接求取$M^n$，时间复杂度不会得到改善，依然是$O(n)$。但我们可以定义矩阵乘法，用快速幂算法来加速$M^n$的求取。

代码

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
class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        vector<vector<int>> q{{1, 1}, {1, 0}};
        vector<vector<int>> res = matrix_pow(q, n - 1);
        return res[0][0];
    }

    vector<vector<int>> matrix_pow(vector<vector<int>>& a, int n) {
        vector<vector<int>> ret{{1, 0}, {0, 1}};
        while (n > 0) {
            if (n & 1) {
                ret = matrix_multiply(ret, a);
            }
            n >>= 1;
            a = matrix_multiply(a, a);
        }
        return ret;
    }

    vector<vector<int>> matrix_multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
        vector<vector<int>> c{{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
};

复杂度分析

  • 时间复杂度$O(logn)$
  • 空间复杂度$O(1)$

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

题目描述

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

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

示例 2：

1
2
输入：n = 7
输出：21

示例 3：

1
2
输入：n = 0
输出：1

提示：

  • 0 <= n <= 100

思路

没什么可说的，分析下来和斐波那契数列不能说毫无关系只能说一模一样。主要是初始状态要注意是1不是0。原地跳也是一种跳法嘛。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numWays(int n) {
        int a=1,b=1,sum=0;
        for(int i=0;i<n;i++){
            sum = (a + b)%1000000007;
            a = b ;
            b = sum;
        }
        return a;
    }
};