note: 虽然本科的时候讲递归必讲斐波那契,但是不意味着递归最适合于斐波那契,因为存在很多重复计算,且递归也需要额外空间。
还有关于求余的问题,有三个公式需要记一下
题目描述
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:
1 | F(0) = 0, F(1) = 1 |
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
1 | 输入:n = 2 |
示例 2:
1 | 输入:n = 5 |
提示:
- 0 <= n <= 100
方法一:递归(容易超时)
思路
简单思维,照搬公式。
需要思考的是哪里复杂了呢?原因是产生了很多重复计算,如下图所示
代码
1 | class Solution { |
复杂度分析
时间复杂度$O(2^n)$。递归出来一个类似于二叉树的结构,时间复杂度近似为二叉树的节点数,根据斐波那契公式和推导,可以知道它的紧确界为$O((\frac{1+\sqrt5}{2})^n)$。中间掺杂有重复计算,参考Krahets的题解图 (leetcode-cn.com)](https://pic.leetcode-cn.com/25e913ab8d7a22bb017669e4a097cf51d10861f365002f2d8556ee7a64464cd8-Picture0.png))
空间复杂度$O(n)$。二叉树的高度
方法二:递归优化,减少重复计算
原理
将计算后的值放入数组进行存储,需要时不用再递归计算。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度:$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 | class Solution { |
复杂度分析
- 时间复杂度$O(n)$。每个值计算一次
- 空间复杂度$O(n)$。需要一个数组存放计算的值。
方法四:动态规划+滚动数组(进一步减少空间,最常用)
原理
事实上分析方法三中的数组,我们发现其实没必要存储所有中间计算过程中的值,因为我们只用得到$n-1$和$n-2$这两个中间值。
所以我们可以使用两个变量来存储,就可以将数组省略掉,这其实是一种滚动数组的思想
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(n)$。每个值计算一次
- 空间复杂度$O(1)$。只使用了常数级别的额外空间。
方法五:矩阵快速幂(不常用)
原理
注意: 本题中这种方法不可用,因为会发生溢出错误(n太大了)
进一步降低时间复杂度的方法。
建立一个递推关系如下所示
因此我们有:
如果令
因此如果我们可以快速计算矩阵M的$n$次幂,就可以得到$F(n)$的值。如果直接求取$M^n$,时间复杂度不会得到改善,依然是$O(n)$。但我们可以定义矩阵乘法,用快速幂算法来加速$M^n$的求取。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(logn)$
- 空间复杂度$O(1)$
剑指 Offer 10- II. 青蛙跳台阶问题
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
1 | 输入:n = 2 |
示例 2:
1 | 输入:n = 7 |
示例 3:
1 | 输入:n = 0 |
提示:
- 0 <= n <= 100
思路
没什么可说的,分析下来和斐波那契数列不能说毫无关系只能说一模一样。主要是初始状态要注意是1不是0。原地跳也是一种跳法嘛。
代码
1 | class Solution { |
原文链接: https://zijian.wang/2021/05/31/10 斐波那契数列和青蛙跳台阶/
版权声明: 转载请注明出处.