这道题上来一个递归，按道理应该是正确的，但是递归会超出时间限制、

<div>
class Solution {
    public int fib(int n) {
        int num = 0;
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        //主函数
        num += fib(n-1) + fib(n-2);
        return num;
    }
}
</div>

下面来看不同的解决方法

=========================

• 滚动数组（动态规划）

这里的滚动数组并不是真的数组，而是三个变量滚动赋值
初始的时候是001，一次后是011，两次过后是112......

<div>
class Solution {
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = (p + q) % MOD; //题目要求要取模
        }
        return r;
    }
}
</div>