描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
下面是 斐波那契数列 的表达式。

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

示例1

输入：
4

返回值：
3

思路

其实思路很明显，就是 斐波那契数列 本身的定义， F(0) = 0, F(1) = 1， F(N) = F(N - 1) + F(N - 2)。
当n >= 2 时，每个数字都是其前面两个数字之和。可以运用动态规划的思想来写这道题。

方法一

可以使用数组来存储每次的数值。最后取值的时候直接取数组小标为 n 对应的值即可。

AC代码

public int Fibonacci(int n) {
        if (n < 0) {
            return  0;
        }
        // 当 n 为 0 或 1 时，直接返回它本身即可
        if (n == 0 || n == 1) {
            return n;
        }
        // 创建一个数组
        int[] dp = new int[n + 1];
        // 初始化下标为 0 和 1 的值
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i ++) {
            // 之后的每个值 都是前两个数值之和
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        // 返回
        return dp[n];
    }

时间复杂度：O(N),N 为数值大小
空间复杂度：O(N)

方法二

大家看上面的方法有没有可以优化的地方。大家可以发现其实每次它只是依赖于前面两个数值，并不用把所有的都需要存储起来。

public int Fibonacci(int n) {
        if (n < 0) {
            return  0;
        }
        // 当 n 为 0 或 1 时，直接返回它本身即可
        if (n == 0 || n == 1) {
            return n;
        }
        // 同理，先初始化前两个
        int dp_0 = 0;
        int dp_1 = 1;
        // 用来存储最终结果
        int result = 0;
        // 开始遍历
         for (int i = 2; i <= n; i ++) {
             // 结果 = 前两个之和
             result = dp_0 + dp_1;
             // 替换
             dp_0 = dp_1;
             dp_1 = result;
         }
        // 返回
        return result;
    }

时间复杂度：O(N),N 为数值大小
空间复杂度：O(1)

最后

这道题运用了动态规划的思想，可以在空间复杂度为O(1)的情况下实现。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。