JZ10 斐波那契数列

JZ10 斐波那契数列

斐波那契数列_牛客题霸_牛客网 (nowcoder.com)

---

// //递归
// public class Solution {
//     public int Fibonacci(int n) {
//         if(n==0) return 0;
//         if(n==1) return 1;
//         if(n==2) return 1;
//         return Fibonacci(n-1)+Fibonacci(n-2);
//     }
// }


// //迭代
// public class Solution {
//     public int Fibonacci(int n) {
//         if(n==0) return 0;
//         if(n==1) return 1;
//         if(n==2) return 1;
//         int first=1;
//         int second=1;
//         int third=0;
//         for(int i=3;i<=n;i++){
//             third=first+second;
//             first=second;
//             second=third;
//         }
//         return third;
//     }
// }


//动规
public class Solution {
    public int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        int[] dp=new int[n+1];
        dp[0]=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];
    }
}