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

题目：

算法

斐波那契数列（Fibonacci sequence），又称黄金分割数列、兔子数列，是数学家列昂纳多·斐波那契于1202年提出的数列。

斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始，每一项都等于前两项之和，递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。

做法

递归

public static int fib0(int n) { if (n<2) { return n; } return fib(n-1) + fib(n-2); }

以上方法会超时，题目要求要加上取模

加上之后：

public int fib(int n) { if (n < 2) return n; int first = fib(n - 1) % 1000000007; int second = fib(n - 2) % 1000000007; return (first + second) % 1000000007; }

此方法可能任然会超时，因为此方法做了很多重复的运算，如果我们吧这种重复的运算都保存下来，需要的时候拿出来用就可以了，节省了很多时间。

public static int fib(int n) { return fib(n, new HashMap()); } public static 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; }

非递归

public static int fib1(int n) { int first = 0; int second = 1; while (n-- > 0) { int temp = first + second; first = second % 1000000007; second = temp % 1000000007; } return first; }