一、题目内容

二、题解

解法1：

思路

dp[i] = dp[i-1] + dp[i-2]
三种方法

1. 递归，时间复杂度n方，计算过的结果还要再次计算
2. 迭代，通过数组记录每次结果，时间、空间都为n

3. 双指针，分别交替充当dp[i-1] + dp[i-2]，另外设变量记录结果

   代码

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