斐波那契数(Java)
2021/9/13 9:04:59
本文主要是介绍斐波那契数(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1
给你 n ,请计算 F(n) 。
解题思路
斐波那契数是一道非常经典的题目,可以使用暴力递归,也可以使用动态规划等方法。本题给出四种解答,分别是
- 代码1 —— 暴力题解
- 代码2 —— 使用带备忘录的递归解法
- 代码3 —— dp数组的动态规划方法
- 代码4 —— 迭代,优化空间复杂度
代码1 —— 暴力题解
class Solution { public int fib(int n) { // base case if (n == 0 || n == 1) { return n; } // 递推关系 return fib(n - 1) + fib(n - 2); } }
时间复杂度:O(2^N)
空间复杂度:O(1)
代码2 —— 带备忘录的递归解法
class Solution { public int fib(int n) { // 备忘录全部初始化为0 int[] memo = new int[n + 1]; // 进行带备忘录的递归 return helper(memo, n); } private int helper(int[] memo, int n) { // base case if (n == 0 || n == 1) { return n; } // 进行检查,已经计算过就不用在计算了 if (memo[n] != 0) { return memo[n]; } memo[n] = helper(memo, n - 1) + helper(memo, n - 2); return memo[n]; } }
时间复杂度:O(N)
空间复杂度:O(N)
代码3 —— 使用 dp 数组的动态规划方法
class Solution { public int fib(int n) { if (n == 0) { return 0; } int[] dp = new int[n + 1]; // base case 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)
空间复杂度:O(N)
代码4 —— 迭代,优化空间复杂度
class Solution { // 优化空间复杂度 public int fib(int n) { if (n == 0 || n == 1) { return n; } // 递推关系 int prev = 0, curr = 1; for (int i = 2; i <= n; i++) { int sum = prev + curr; prev = curr; curr = sum; } return curr; } }
时间复杂度:O(N)
空间复杂度:O(1)
这篇关于斐波那契数(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?