Lintcode 366:fibonacci Fibonacci sequence

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

This problem belongs to dynamic programming , There are two ways , recursive （ Overtime ） And non recursive .

recursive ：

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        if(n==1)
            return 0;
        else if(n==2)
            return 1;
        else
            return fibonacci(n-1) + fibonacci(n-2);
    }
}

Non recursive ：

self：

public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public static int[] f = new int[1000];
    public int fibonacci(int n) {
        // write your code here
        for(int i = 0;i < f.length; ++i){
            f[i] = -1;
        }
        return search(n);
        
    }
    public int search(int n){
        if(f[n] >= 0)
            return f[n];
        else if(n == 1)
            f[n] = 0;
        else if(n == 2)
            f[n] = 1;
        else
            f[n] = search(n - 1) + search(n - 2);
        return f[n];
    }
}

reference：(better)

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        if(n==1)
            return 0;
        if(n==2)
            return 1;
        int f0 = 0;
        int f1 = 1;
        int i = 3;
        int f = 0;
        while(i<=n){
            f = f0 + f1;
            f0 = f1;
            f1 = f;
            i++;
        }
        return f;
    }
}