[Vssue]0509.斐波那契数.md

[youngyangyang04]

https://www.programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html

[Du1in9]

class Solution {
    public int fib(int n) {
        if (N < 2) return n;
        return fib(N - 1) + fib(N - 2);
    }
}

[WilsoEdwards]

LeetCode这道题需要取模 还挺逆天的

[ZYKWLJ]

class Solution {
    public int fib(int n) {
        // return byRecursion(n);
        // return byIteration(n);
       return byDP(n);
    }

    int byRecursion(int n){
        if(n<2)return n;
        return fib(n-1)+fib(n-2);
    }

    int byIteration(int n){
        if(n<2)return n;
        int f1=0,f2=1,f12=1;
        for(int i=2;i<=n;i++){
            f12=f1+f2;
            f1=f2;
            f2=f12;

        }
        return f12;
    }

    int byDP(int n){
        if(n<2)return n;
        int[] dp=new int[n+1];
         dp[0]=0;
         dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-2]+dp[i-1];
        }
        return dp[n];
    }      
}