200928剑指Offer学习总结：斐波那契数列
200928算法学习总结：斐波那契数列
1. 原题目：
剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 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：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
2. 题目分析
我们都知道，传统的递归方式十分耗时，本题中不能直接使用这种方式，会超时。因此我们可以有两种方式进行优化：
（1）非递归方式
a、b分别表示数列中第一个和第二个数，for循环循环n次，每次sum都等于a、b的和，然后a的值来自于b，b的值来自于sum，如此循环，我们最终得到的第n个数就是a。
class Solution {
public int fib(int n) {
int a = 0, b = 1, sum;
for(int i = 0; i < n; i++){
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
优化：可以不用sum中间数，直接使用a、b两个数循环。
class Solution {
public int fib(int n) {
int ans0=0,ans1=1;//分别代表第一个数、第二个数，
if(n==0||n==1){
return n;
}
for(int i=0;i<n;i++){
ans1=ans1+ans0;//1 2 3 5 8 13
ans0=ans1-ans0;//1 1 2 3 5 8
ans1%=1000000007;
}
return ans0;
}
}
（2）优化的递归方式
正如前面说的，递归会超时，那么为什么会这样呢？事实上我们可以想到递归是如何计算的：
如上图所示，在递归计算中会重复计算很多值，比如从F6向下计算F5和F4时，F5递归计算F4和F3，这时F4就被重复计算了，那么我们只需要把计算过的值记录下来，后面遇到同样的计算时直接把值传过去、不再计算，这样就能降低时间复杂度。
存储时可以使用map，如下。也可以使用数组，这种方法需要额外的空间。
public int fib(int n, Map<Integer, Integer> map) {
if (n < 2)
return n;
if (map.containsKey(n))
return map.get(n);
int first = fib(n - 1, map) % 1000000007;
map.put(n - 1, first);
int second = fib(n - 2, map) % 1000000007;
map.put(n - 2, second);
int res = (first + second) % 1000000007;
map.put(n, res);
return res;
}
图片及map代码出处：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/di-gui-he-fei-di-gui-liang-chong-fang-shi-du-ji-ba/
3. 总结
递归的优化（记忆化的递归）方式，能够避免递归中的重复计算。
4. 拓展：青蛙跳台阶问题
剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
这道题是一个斐波那契数列的变形，有两点不同：
- 特殊要求第零项是1，而不是0，但是我们为了使用斐波那契的规律，依然在计算时把第零项当作0，然后最后的结果上我们加1。
- 得到的到达第n个台阶情况是前面所有斐波那契数的和，最后要求和。
代码如下。
class Solution {
public int numWays(int n) {
int ans0=0,ans1=1;//分别代表第一个数、第二个数，
int ans2=1;//最终结果
if(n<=1){
return 1;
}
for(int i=0;i<n;i++){//从n=1开始
ans2+=ans0; // 3 5 8 13 21
ans2%=1000000007;
ans1=ans1+ans0;//1 1 1 2 3 5 8 13
ans0=ans1-ans0;// 1 1 2 3 5 8
ans1%=1000000007;
}
return ans2;
}
}