每日算法一题之斐波那契数列

记得多年前面试的时候就在手写斐波那契数列上栽过，今天就趁这机会在这总结下。这题虽是老生常谈了，

但相信我这里分享的一定会给自己和你们一个温故而知新的机会。

题目描述

斐波那契数列是一位意大利的数学家，他闲着没事去研究兔子繁殖的过程，研究着就发现，可以写成这么一个序列：1，1，2，3，5，8，13，21… 也就是每个数等于它前两个数之和。那么给你第 n 个数，问 F(n) 是多少。

解析

首先我们给一个通用的解法：

class Solution {
  public int fib(int N) {
      if (N == 0) {
          return 0;
      } else if (N == 1) {
          return 1;
      }
      return fib(N-1) + fib(N-2);
  }
}

这个算法的复杂度太高了，有些函数会重复执行的。

优化算法

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

参考资料：

1. 这才是面试官想听的：详解「递归」正确的打开方式