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

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;
}
};