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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
写一个函数，输入 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
 

提示：

0 <= n <= 100

这是一个典型的递归问题，但是递归算法往往不是最优的

递归法

原理：把 f(n)f(n) 问题的计算拆分成 f(n-1)f(n−1) 和 f(n-2)f(n−2) 两个子问题的计算，并递归，以 f(0) 和 f(1)为终止条件。

缺点：

  1. 有大量的重复的递归计算
  2. 递归一直嵌套，效率比较低
Picture0.png 
1
2
3
4
5
6
7
8
9
10
//1.0版本 递归版本
  // leetcode：超出时间限制
  public static int fib(int n) {
      if (n == 0) {
          return 0;
      } else if (n == 1) {
          return 1;
      }
      return fib(n - 1) + fib(n - 2);
  }
1
2
3
4
5
6
7
8
//2.0版本 递归版本
// leetcode：超出时间限制
public static int fibV2(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

记忆化递归法

原理：在递归算法的基础上，新建一个长度为n的数组，用于在递归是存储f(0)至 f(n)的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。

缺点：

  1. 递归一直嵌套，效率比较低
  2. 记忆化存储需要使用O（N）的额外空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//3.0版本 记忆化递归
// 解决递归版本中的重复计算递归的值
// leetcode：超出时间限制
public static int fibV3(int n) {
    if (n < 2) {
        return n;
    }
    int[] memorization = new int[n + 1];
    memorization[0] = 0;
    memorization[1] = 1;
    return myFibonacci(n, memorization);
}

private static int myFibonacci(int n, int[] memorization) {
    if (n < 2 || memorization[n] > 0) {
        return memorization[n];
    }
    memorization[n] = (myFibonacci(n - 1, memorization) + myFibonacci(n - 2, memorization))%1000000007;
    return memorization[n];
}

动态规划

原理：以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。

递归算法是一种倒序进行，直接进行 f(n)的计算，在 f(n)的计算过程中进行递归，求解f(n - 1)和f(n - 2)的值，而且递归算法本身就不适合大数据量的计算容易造成栈移出

而动态规划怎事从f(0)开始，逐渐求解f(n)的过程

从计算效率、空间复杂度上看，动态规划是本题的最佳解法。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 4.0版本 动态规划
// 
// leetcode：超出40%提交
public static int fibV4(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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//5.0版本 动态规划
// 解决动态规划重复计算问题
// leetcode：超出40%提交
// 这种没有太大的意义，因为动态规划算法没有重复的值得计算
public static int fibV5(int n) {
    if (n < 2) {
        return n;
    }
    int[] memorization = new int[n + 1];
    memorization[0] = 0;
    memorization[1] = 1;
    for (int i = 2; i <= n; i++) {
        memorization[i] = (memorization[i-1] + memorization[i - 2])%1000000007;
    }
    return memorization[n];
}

博客首先发布于：

https://lvxiaoyi.top/