Fibonacci

Find the Nth number in Fibonacci sequence.

Discussion

根据公式递归非常简单，唯一需要注意的是f(1)=0，而不是f(0)=0，因为没有第0个。。。

Solution - Recersion

int fibonacci(int n) {
        if(n<=2) return n-1;
        return fibonacci(n-1) + fibonacci(n-2);
    }

Follow up

画递归调用树，可以看出有大量重复的计算，时间复杂度是O(2^N),显然效率太低了。而我们知道动归是可以减少这种重复计算的。下面给出算法。

Solution - DP

//O(n) rum time
//O(n) space
int fibonacci(int n) {
        if(n<=2) return n-1;
        vector<int> f(n+1, 0);
        f[1] = 0;
        f[2] = 1;
        for(int i=3; i<=n; i++) {
            f[i] = f[i-2] + f[i-1];
        }
        return f[n];
}

普通动归总是可以改进space的，这个也不例外。

//O(n) rum time
//O(1) space
    int fibonacci(int n) {
        if(n<=2) return n-1;
        int a = 0;
        int b = 1;
        int result = 0;
        for(int i=3; i<=n; i++) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }