递归
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int Fibonacci (int n) { // write code here if(n<=2) return 1; return Fibonacci(n-1)+Fibonacci((n-2)); } }
动态规划
存储
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int Fibonacci (int n) { // write code here int[] dp=new int[50]; Arrays.fill(dp,0); dp[1]=1; dp[2]=1; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; } }
优化
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int Fibonacci (int n) { // write code here if(n<=2){ return 1; } int a=1; int b=1; int c=1; for(int i=3;i<=n;i++){ c=a+b; a=b; b=c; } return c; } }