大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围:
要求:空间复杂度 ,时间复杂度 ,本题也有时间复杂度 的解法
一个正整数n
输出一个正整数。
4
3
根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案为3。
1
1
2
1
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int Fibonacci (int n) { // write code here double squareRoot = Math.sqrt(5); double a = (1 + squareRoot) / 2; double b = (1 - squareRoot) / 2; double res = (1 / squareRoot) * (Math.pow(a, n) - Math.pow(b, n)); return (int)Math.floor(res); } }
public int Fibonacci (int n) { int[] dp=new int[n]; dp[0]=1; dp[1]=1; for(int i=2;i<n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n-1]; } }
public class Solution { public int Fibonacci(int n) { if(n<=2) return 1; int []dp=new int[n+1]; dp[1]=dp[2]=1; for(int i=3;i<=n;i++) dp[i]=dp[i-1]+dp[i-2]; return dp[n]; } /*public int Fibonacci(int n) { if(n<=2) return 1; else return Fibonacci(n-1)+Fibonacci(n-2); }*/ }
public class Solution { public int Fibonacci(int n) { // 1.递归 // 2.记录table int[] table = new int[n]; return fib(n, table); } private int fib(int n, int[]table) { // 递归结束条件 if (n == 1 || n == 2) { return 1; } // 数组中存在,直接返回,避免重复计算 if (table[n - 1] != 0) { return table[n - 1]; } int res = fib(n - 1, table) + fib(n - 2, table); // 结果保存进数组,以免重复计算 table[n - 1] = res; return res; } }
public class Solution { public int Fibonacci(int n) { if(n <= 2){ return 1; } // 初始化前两个数 int pre = 1, last = 1; // temp用于存储每次相加后的新数 int temp; for(int i = 2; i < n; i++){ // 得到下一个数 temp = pre + last; // 下面两步即为向后移动 // pre等于last pre = last; // last等于当前计算好的下一个数 last = temp; } // 最终返回last return last; } }
public class Solution { public int Fibonacci(int n) { int first = 1; int second = 1; int third = 2; for (int i = 3; i < n; i++) { first = second; second = third; third = first + second; } return n == 1 ? 1 : n == 2 ? 1 : third; } }