斐波那契数

题目

具体思路

1. 根据 res[n] 生成的方式，动态模拟并得到所有的 res[] ;
2. 要想得到第 n 个数，我们需要计算前 n 个所有的数;
3. 要是只想得到第 n 个数，我们可以不用保存中间结果。

具体实现

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

这里我们直接计算并保存所有的中间生成结果；初始化一个 res[1] ,然后我们这边的初始数组需要多申请一个 ， 即 n + 2 ，目的是让 res[1] 可以正常初始化。

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int pre = 0;
        int next = 1;
        int res = -1;
        for (int i = 2; i <= n; i++) {
            res = pre + next;
            pre = next;
            next = res;
        }
        return res;
    }
}

这里我们使用两个中间的变量来保存结果，同时对初始化进行特殊处理。