# Fibonacci ### Source - lintcode: [(366) Fibonacci](http://www.lintcode.com/en/problem/fibonacci/) ~~~ Find the Nth number in Fibonacci sequence. A Fibonacci sequence is defined as follow: The first two numbers are 0 and 1. The i th number is the sum of i-1 th number and i-2 th number. The first ten numbers in Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... Example Given 1, return 0 Given 2, return 1 Given 10, return 34 Note The Nth fibonacci number won't exceed the max value of signed 32-bit integer in the test cases. ~~~ ### 題解 斐波那契數列使用遞歸極其容易實現，其實使用非遞歸的方法也很容易，不斷向前滾動即可。 ### Java ~~~ class Solution { /** * @param n: an integer * @return an integer f(n) */ public int fibonacci(int n) { if (n < 0) return -1; if (n == 1) return 0; if (n == 2) return 1; int fn = 0, fn1 = 1, fn2 = 0; for (int i = 3; i <= n; i++) { fn = fn1 + fn2; fn2 = fn1; fn1 = fn; } return fn; } } ~~~ ### 源碼分析 1. corner cases 1. 初始化 fn, fn1, fn2, 建立地推關系。 1. 注意 fn, fn2, fn1的遞推順序。 ### 復雜度分析 遍歷一次，時間復雜度為 O(n)O(n)O(n), 使用了兩個額外變量，空間復雜度為 O(1)O(1)O(1).