斐波那契数列 I

题目链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

题目解析
这道题目采用动态规划的思路进行解答，题目中已经给出了公式和基础的起始值。

public int fib(int n) {
        // F(N) = F(N-1) + F(N-2)

        if (n <2){
            return  n;
        }
        final int MOD = 1000000007;
        //fn2 对应F(n-2)
        //fn1 对应F(n-1)
        //fn 对应F(n)
        int fn2 =0,fn1 = 0,fn = 1;
        for (int i = 2;i<=n;i++){
            fn2 = fn1;
            fn1 = fn;
            fn = (fn2 + fn1) % MOD;
        }

        return fn;

    }

复杂度分析
空间复杂度: O(N)。
时间复杂度: O(1)。