介绍

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。

题解

循环迭代法

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int a = 0, b = 1, sum = 0;
        for (int i = 2; i <= n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return sum;
    }
}

多路递归-优化-记忆法

/**
     * 使用 Memoization(记忆法，也称备忘录)改进
     */
    public static int fibonacci(int n) {
        if(n==0){
            return 0;
        }
        int[] cache = new int[n + 1];
        Arrays.fill(cache,-1);
        cache[0]=0;
        cache[1]=1;
        return f(n, cache);
    }


    /**
     * 递归求斐波那契第n项
     */
    public static int f(int n,int[] cache){
        /*if (n==0) {
            return 0;
        }
        if (n==1) {
            return 1;
        }*/
        if (cache[n] != -1) {
            return cache[n];
        }
        cache[n] = f(n - 1, cache) + f(n - 2, cache);
        return cache[n];
    }

笔记

求出sum，滑动刷新a,b的值（向左覆盖一位
以sum为参照物：
a = b; // 将前一项的值赋给前前项
b = sum; // 将新计算的值赋给前一项
那么就可以求出下一个sum

变体

兔子问题，青蛙爬楼梯