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

解题思路一：递归

虽然递归并不是本题的考点，不过探究递归写法的时间复杂度和空间复杂度是很有意义的

我们以求解fib(5) 列举下整个递归的调用：

  1.                         fib(5)
  2.                  /                 \
  3.                fib(4)               fib(3)
  4.             /          \            /    \
  5.          fib(3)      fib(2)        fib(2) fib(1)
  6.        /    \       /     \       /    \
  7.     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
  8.    /    \
  9. fib(1)  fib(0)

代码

  1. class Solution {
  2.     public int fib(int n) {
  3.         if(n == 0){
  4.             return 0;
  5.         }
  6.         if(n == 1){
  7.             return 1;
  8.         }
  9.         return (fib(n - 1) + fib(n - 2)) % 1000000007;
  10.     }
  11. }

复杂度分析

  • 时间复杂度：O(2 ^ N)

不难看出求解斐波那契数列的递归调用类似于求一棵二叉树的节点的个数，其时间复杂度为：O(2 ^ N)

  • 空间复杂度：O(K)

占用额外空间是递归栈的深度，类似于求解二叉树的高度，空间复杂度为：O(K)

解题思路二：动态规划

动态规划三大步：

  1. 定义状态转移方程
  2. 给定方程初始值
  3. 递推实现

定义dp数组，其中dp[i]表示斐波那契数列的第i项

状态转移方程为:

  1. dp[i] = dp[i - 1] + dp[i - 2]

最终返回结果为：dp[n]

方程初始值为：

  1.  dp[0] = 0
  2.  dp[1] = 1

代码

Java

  1. class Solution {
  2.     public int fib(int n) {
  3.         if(n == 0){
  4.             return 0;
  5.         }
  6.         if(n == 1){
  7.             return 1;
  8.         }
  9.         // dp[i] 表示 斐波那契数列的第i项
  10.         // dp[i] = dp[i - 1] + dp[i - 2]
  11.         // 最终返回的结果为:dp[n]
  12.         int[] dp = new int[n + 1];
  13.         dp[0] = 0;
  14.         dp[1] = 1;
  15.         for(int i = 2; i < n + 1; i++){
  16.             dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007 ;
  17.         }
  18.         return dp[n];
  19.     }
  20. }

复杂度分析

  • 时间复杂度：O(N)

我们要通过 N 次计算才能得到斐波那契数列的第 N 项，时间复杂度为：O(N)

  • 空间复杂度：O(N)

开辟 dp 数组，占用额外的空间为：O(N)