JZ10 斐波那契数列

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

// //fib
// //fib(1)-1
// //fib(2)-1
// //fib(3)-2
// //递归
// 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);
//     }
// }


// //递归-使用map剪枝
noac
// import java.util.HashMap;
// public class Solution {
//     public int Fibonacci(int n) {
//         if(n==0){
//             return 0;
//         }
//         if(n==1){
//             return 1;
//         }
//         if(n==2){
//             return 1;
//         }
//         HashMap<Integer,Integer> map=new HashMap<>();
//         int first=0;
//         if(map.containsKey(n-2)){
//             first=map.get(n-2); 
//         }else{
//             first=Fibonacci(n-2);
//             map.put(n-2,first);
//         }
//         int second=0;
//         if(map.containsKey(n-1)){
//             second=map.get(n-1);
//         }else{
//             second=Fibonacci(n-1);
//             map.put(n-1,second);
//         }  
//         return first+second;
//     }
// }


//迭代
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;
        while(n>2){
            third=first+second;
            first=second;
            second=third;
            n--;
        }
        return third;
    }
}