递归

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;
        
    }
}