题解 | #斐波那契数列#--递归+动态规划及其优化版

public class Solution {
    public int Fibonacci(int n) {
        /*//方法一：递归法，比较直白,时间复杂度为o(2^n)
        if(n==1){
            return 1;
        }
        if(n==2){
            return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);*/
        /*//方法二：动态规划法--时间复杂度和空间复杂度均为o(n)
        if(n==1||n==2){
            return 1;
        }
        int[] arr=new int[n+1]; //n=0时，为0
        arr[0]=0;
        arr[1]=1;
        arr[2]=1;
        for(int i=3;i<=n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];*/
        
        //方法三：动态规划法优化版--把空间复杂度降为o(1)--只需要用到三个变量
        if(n==1||n==2){
            return 1;
        }
         int f1=1;
        int f2=1;
        int fn=0;
        for(int i=3;i<=n;i++){
            fn=f1+f2;
            f1=f2;
            f2=fn;
        }
        return fn;
    }
}