剑指 Offer 10- I. 斐波那契数列

剑指 Offer 10- I. 斐波那契数列

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50fji7/

递归

class Solution {
    // 用于缓存计算结果，防止重复计算
    int[] catchs = new int[100];
    public int fib(int n) {
          // 递归终止条件
        if (n <= 1) {
            return n;
        }
        // 先判断缓存是否存在，如果没有不存在再递归计算
        if (catchs[n - 1] < 1) {
            catchs[n - 1] = fib(n - 1);
        }
        if (catchs[n - 2] < 1) {
            catchs[n - 2] = fib(n - 2);
        }
        // 直接拿缓存结果相加，题目还要求取模再返回
        return (catchs[n - 1] + catchs[n - 2]) % 1000000007;
    }
}

遍历

class Solution {
    public int fib(int n) {
        // 定义 n = 0 与 n = 1 的结果
        int a = 0, b = 1, res = 0;
        for (int i = 0; i < n - 1; i ++) {
            res = (a + b) % 1000000007;
            a = b;
            b = res;
        }
        return res;
    }
}