leetcode-509. 斐波那契数

JAVA解法

class Solution {
    public int fib(int n) {
        // 小于 2 为本身
        if (n < 2) {
            return n;
        }
        // F(n) = F(n−1) + F(n−2)
        int fn2 = 0, fn1 = 0, fn = 1;
        for (int i = 2; i <= n; ++i) {
            fn2 = fn1; 
            fn1 = fn; 
            fn = fn2 + fn1;
        }
        return fn;
    }
}

题解分析

斐波那契数列的特性：
F(0) = 0，F(1) = 1,当 n < 2 时,F(n) = F(n - 1) + F(n - 2)，其中 n > 1

我们可以构造一个赋值，让前一个的值加上当前的值等于下一个的值，然后把当前值赋给前一个，下一个的值赋值给当前值，然后下一轮相加就符合 F(n) = F(n−1) + F(n−2) 实现斐波那契数列。

leetcode原题： 509. 斐波那契数