LeetCode_111_FibonacciNumber

1. question: 斐波那契数（简单）

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fibonacci-number

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

2. answers

这道题还是比较简单的，因为题目中准确描述了递推关系，所以可直接递归或者迭代。（注意，这题算是动态规划的入门案例。）

递推关系可以按照递归来实现，递归终止条件就是初始的两个数。代码如下所示：

public class Solution_0111 {

    public int fib(int n) {

        if(n == 0 || n == 1) return n;
        else return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {

        Solution_0111 s = new Solution_0111();

        System.out.println(s.fib(1));

    }
}

虽然递归比较简单，但是仔细分析，可以发现，实际上存在重复运算，比如F(n) = F(n-1) + F(n-2)，但是F(n-1) = F(n-2) + F(n-3)，因此，可以看到对于F(n-2)则会进行两次递归运算。可采用迭代直接递推即可。代码如下所示：

public class Solution_0111_02 {

    public int fib(int n) {

        if(n == 0 || n == 1) return n;

        // 初始化两个基础元素。
        int pre = 0;
        int post = 1;

        // 第N个数，存储第N个值。
        int fibN = 0;

        for (int i = 2; i <= n; i++) {

            // 递推演变
            fibN = pre + post;
            pre = post;
            post = fibN;
        }

        return fibN;
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0111_02 s = new Solution_0111_02();

        System.out.println(s.fib(4));
    }
}

虽然迭代和递归在数量级上是一致的，但是似乎递归是O(2n)，还是有一点点差距的。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。