题解 | #斐波那契数列#

递归

优化思路：将f(n)的存到数组中，避免重复计算

public class Solution {
    int[] f=new int[41];
    public int Fibonacci(int n) {
        if(n==1||n==2) return 1;
        return f[n]=Fibonacci(n-1)+Fibonacci(n-2);
    }
}

非递归

优化思路1：使用数组进行存储

public class Solution {
    public int Fibonacci(int n) {
        int[] dp=new int[41];
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return di[n];
    }
}

优化思路2：非递归从n=3开始，逐级向上，最终到达n,每次计算只使用到n-1、n-2两个值，可以简化存储空间

public class Solution {
    public int Fibonacci(int n) {
        if(n<=2)return 1;
        int a = 1;
        int b = 1;
        int c=0;
        for(int i=3;i<=n;i++){
            c=a+b;
            a=c-a;
            b=c;
            
        }
        return c;
    }
}