Fibonacci Number Solutions in C++

// Source : https://leetcode.com/problems/fibonacci-number/
// Author : Hao Chen
// Date   : 2019-03-26



class Solution {
public:
    int fib(int N) {
        if (N < 2 )  return N;
        int first = 0, second = 1;

        for ( N-=1; N > 0; N-- ) {
            second += first;
            first = second - first;
        }
        return second;
    }
};

/// Source : https://leetcode.com/problems/fibonacci-number/
/// Author : liuyubobobo
/// Time   : 2019-01-09

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int fib(int N) {

        vector<int> dp(N + 1, -1);
        dp[0] = 0;
        dp[1] = 1;
        return dfs(N, dp);
    }

private:
    int dfs(int N, vector<int>& dp){

        if(N <= 1) return N;
        if(dp[N] >= 0) return dp[N];
        return dp[N] = dfs(N - 1, dp) + dfs(N - 2, dp);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/fibonacci-number/
/// Author : liuyubobobo
/// Time   : 2019-01-09

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int fib(int N) {

        vector<int> dp(N + 1, -1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= N; i ++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[N];
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/fibonacci-number/
/// Author : liuyubobobo
/// Time   : 2019-01-09

#include <iostream>
#include <vector>

using namespace std;


/// Binets Method
/// | F(n+1) F(n)   | = | 1 1 |^n
/// | F(n)   F(n-1) |   | 1 0 |
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int fib(int N) {

        if(N <= 1) return N;

        int prev = 0, cur = 1;
        for (int i = 2; i <= N; i++) {
            int f = cur + prev;
            prev = cur;
            cur = f;
        }
        return cur;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/fibonacci-number/
/// Author : liuyubobobo
/// Time   : 2019-01-09

#include <iostream>
#include <vector>

using namespace std;


/// Binets Method
/// | F(n+1) F(n)   | = | 1 1 |^n
/// | F(n)   F(n-1) |   | 1 0 |
///
/// Time Complexity: O(logn)
/// Space Complexity: O(logn)
class Solution {
public:
    int fib(int N) {

        if(N <= 1) return N;

        vector<vector<int>> base = {{1, 1},
                                    {1, 0}};
        return matrix_pow(base, N - 1)[0][0];
    }

private:
    vector<vector<int>> matrix_pow(const vector<vector<int>> &m, int n) {

        if (n == 1)
            return m;

        vector<vector<int>> t = matrix_pow(m, n / 2);
        vector<vector<int>> res = matrix_multiply(t, t);
        if (n % 2)
            return matrix_multiply(res, m);
        return res;
    }

    vector<vector<int>> matrix_multiply(const vector<vector<int>> &m1,
                                        const vector<vector<int>> &m2) {

        vector<vector<int>> res(2, vector<int>(2, 0));
        res[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
        res[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
        res[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
        res[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/fibonacci-number/
/// Author : liuyubobobo
/// Time   : 2019-01-09

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


/// Closed Form
/// https://en.wikipedia.org/wiki/Fibonacci_number
///
/// Time Complexity: O(logn)
/// Space Complexity: O(logn)
class Solution {
public:
    int fib(int N) {

        double a = (1. + sqrt(5.)) / 2.0;
        double b = (1. - sqrt(5.)) / 2.0;
        return (int)((pow(a, N) - pow(b, N)) / sqrt(5) + 0.5);
    }
};


int main() {

    return 0;
}