描述
大家都知道斐波那契数列,现在要求输入一个整数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)的情况下实现。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。