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) {

        // write your code here

        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);
        }        
    }

Read full article from Lintcode Fibonacci - Bogart2015 - 博客园