剑指Offer 10-Ⅰ斐波那契数列

前言

在leetcode上做了几天题了，每天一道简单和中等，没有一题是独立做出来的。BUT！今天，我站起来了，我终于独立完成一个题了。

好吧，虽然这题很简单T-T，来看看题目。

纵使简单，我依旧提交了四次才对，没考虑到一些边界case。

分析题目

斐波那契数列的特点是每一项等于前两项之和，也就是说每一项都可以由前两项推导出来，动态规划的味道有没有。

解法1

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] res = new int[n + 1];
        res[0] = 0;
        res[1] = 1;
        int mod = 1000000007;
        for (int i = 2; i <= n; i++) {
            res[i] = (res[i - 1] + res[i - 2]) % mod;
        }
        return res[n];
    }
}

我想到的是这样的解法，时间复杂度和空间复杂度都是O(N)。

解法2

class Solution {
    public int fib(int n) {
        if(n == 0) return 0;
        int fn0 = 0;
        int fn1 = 1;
        int temp;
        for(int i = 2; i <= n; i++){
            temp = fn0 + fn1;
            fn0 = fn1;
            fn1 = temp% 1000000007; // 每次运算都取模 避免越界
        }
        return fn1;
    }
}

评论区的另一种解法，fn0和fn1两个难兄难弟一前一后往前走，不用定义数组，时间复杂度是O(N)，空间复杂度O(1)，妙啊。