## Monday, January 11, 2016

### Lintcode Fibonacci - Bogart2015 - 博客园

Lintcode Fibonacci - Bogart2015 - 博客园
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.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
`    Fn = Fn-1 + Fn-2`
with seed values
`   F1 = 0 and F2 = 1`
```int fibonacci(int n) {
if (n == 1)
return 0;
else if (n == 2)
return 1;
return fib(n-1) + fib(n-2);
}```
Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential. So this is a bad implementation for nth Fibonacci number.
Extra Space: O(n) if we consider the function call stack size, otherwise O(1).
Method 2 ( Use Dynamic Programming )
```int fibonacci(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[n+1];
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[1] = 0;
f[2] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}```
Method 3 ( Space Otimized Method 2)
We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibannaci number in series.
```int fibonacci(int n)
{
int a = 0, b = 1, c, i;
if( n == 1) return a; ```
`  if( n == 2) return b; `
```  for (i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}```
http://cherylintcode.blogspot.com/2015/06/fibonacci.html
public int fibonacci(int n) {
if(n <= 2) return n - 1;
int pre = 0, cur = 1;
for(int i = 3; i <= n; i++){
int temp = cur;
if(Integer.MAX_VALUE - pre < cur) return Integer.MAX_VALUE;
cur = pre +cur;
pre = temp;
}
return cur;
}
http://blog.csdn.net/willshine19/article/details/46907199
```    HashMap<Integer, Integer> map;
public int fibonacci(int n) {
// 2015-07-16
// 用哈希表提高时间效率，算过的值就保存下来，不用再算
// 注意递归要向“已知”的方向
if (map == null) {
map = new HashMap<>();
}
if (n <= 0) {
return -1;
} else if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
if (!map.containsKey(n - 1)) {
map.put(n - 1, fibonacci(n - 1));
}
if (!map.containsKey(n - 2)) {
map.put(n - 2, fibonacci(n - 2));
}
return map.get(n - 1) + map.get(n - 2);
}
}```