思路

1. 根据出名的斐波那契公式实现 F(n) = F(n-1) + F(n-2)
2. 递归调用该题会超时，使用map存储计算结果会浪费空间

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
	// 使用三个变量记录f(n-2) f(n-1) f(n)
        int p,q,r;
        p = 0;
        q = 1;
        r = 0;
        // 遍历到n
        int index = 2;
        while(index <= n) {
            // 题目要求取模
            r = (p + q)%1000000007 ;
            p = q;
            q = r;
            index ++;
        }
        return r;
    }
}

思路2:

1. 思路1的时间复杂度为O(n),但是思路2可以实现O(logn)的时间复杂度。涉及矩阵运算，这里给出思路链接 矩阵快速幂 有兴趣的可以去看看

Q.E.D.