剑指 Offer 10- I. 斐波那契数列（简单，动态规划）

剑指 Offer 10- I. 斐波那契数列（简单，动态规划）

题目链接：剑指 Offer 10- I. 斐波那契数列

递归会超出时间限。
官方有两种解法，只能看懂第一种动态规划

class Solution {
public:
    int fib(int n) {
        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;
    }
};