leetcode | 509题 | 斐波那契数

//方法一
// class Solution {
// public:
//     int fib(int N) {
//         if(N == 0)
//         {
//             return 0;
//         }
//         if(N == 1)
//         {
//             return 1;
//         }
//         if(N == 2)
//         {
//             return 1;
//         }
//         return fib(N - 1) + fib(N - 2);
//     }
// };

//方法二
// class Solution {
// public:
//     int fib(int N) {
//         if(N <= 1)
//         {
//             return N;
//         }
//         return fib(N - 1) + fib(N - 2);
//     }
// };

//方法三
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int g = 0;
        int f = 1;
        for (int i = 2; i <= N; ++i)
        {
            f = f + g;
            g = f - g;
        }
        return f;
    }
};