难度

简单

思路

递归

  • 斐波那契数列的递推式本身就符合 递归 定义，因此可直接写出。
  • 问题
    • 简单的递归方式显然不是此问题的最优解，因为它会重复计算。

斐波那契数列_递归.png

  • 而且时间复杂度很高，指数级。
    1. private static int fib_1(int n) {
    2.   return n < 2 ? 1 : fib_1(n-1) + fib_2(n - 2);
    3. }
    | 时间复杂度 | O(2**)** | | —- | —- | | 空间复杂度 | O(n) |

动态规划

  • 动态规划 并非此问题的最优解，但是我们能用动态规划写出就算是最优解。

    1. public static int fib_2(int n) {
    2.   if (n == 0) return 0;
    3.   if (n == 1) return 1;
    4.   int[] dp = new int[n + 1];
    5.   dp[0] = 0;
    6.   dp[1] = 1;
    7.   for (int i = 1; i < n; i++) {
    8.       dp[i+1] = dp[i] + dp[i-1];
    9.       dp[i+1] %= 1000000007;
    10.   }
    12.   return dp[n];
    13. }

    | 时间复杂度 | O(n) | | —- | —- | | 空间复杂度 | O(n) |

总结

  • 需要加深对 动态规划 的理解，现在虽然能根据题目写出动态规划递推式，但是还是知其然不知其所以然，往后需要加深原理的理解。
  • 斐波那契数列 也包含了数据之美，详戳