斐波拉契数的几种求法

斐波拉契数列求法的题目有：

• 509 斐波拉契
• 面试题10-1 斐波拉契数列
• 70 爬楼梯

解法一：

傻递归

public class Solution {
    public int fib(int N) {
        if (N < 2) return N;
        return fib(N - 1) + fib(N - 2);
    }
}

解法二：

带缓存的递归

public class Solution {

    //缓存
    static int[] cache;

    public int fib(int N) {
        //初始化缓存
        cache = new int[N + 1];
        return myfib(N);
    }

    public int myfib(int n) {
        //退出条件
        if (n <= 1) {
            cache[n] = n;
            return cache[n];
        }
        //如果不存在就递归调用存入缓存
        if (cache[n] == 0){
            cache[n] = myfib(n-1)+myfib(n-2);
        }
        return cache[n];
    }
}

解法三

迭代法：

public class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int f0 = 0;
        int f1 = 1;
        int f2 = 0;

        for (int i = 2; i <= n; i++) {
            f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }
        return f2;
    }
}