#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

// You are climbing a staircase. It takes n steps to reach the
// top. Each time you can either climb 1 or 2 steps. In how many
// distinct ways can you climb to the top?

/*
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Hint:
To reach nth step, what could have been your previous steps? (Think
about the step sizes)

n = 1: 1

n = 2: 1 1
       2
       --
       2 combinations

n = 3: 1 1 1
       1 2
       2 1
       ----
       3 combinations

n = 4: 1 1 1 1,    four '1's
       1 1 2,      two '1's, one '2',   --> 3 total combinations
       1 2 1
       2 1 1,
       2 2         two '2's
       ------
       5 combinations

n = 5: 1 1 1 1 1,  five '1's
       1 1 1 2,    three '1's, one '2',  --> 4 total combinations
       1 1 2 1,
       1 2 1 1,
       2 1 1 1,
       2 2 1,      one '1', two '2's,     --> 3 total combinations
       2 1 2,
       1 2 2,
       ---------
       8 combinations

n = 6: 1 1 1 1 1 1    six '1's

       1 1 1 1 2      four '1's, one '2' --> 5 combinations
       1 1 1 2 1
       1 1 2 1 1
       1 2 1 1 1
       2 1 1 1 1

       2 2 1 1        two '1's, two '2's  -->  6 combinations
       2 1 2 1
       2 1 1 2       
       1 2 2 1      
       1 2 1 2       
       1 1 2 2
       
       2 2 2,         three '2's
       -------------
       13 combinations
       

Guess what, the number of combinations for a n steps to the top
resembles a fibonacci sequence.
   n=1 -> F(2), n=2 -> F(3), n=3 -> F(4) ... n -> F(n+1)

The Fibonacci numbers may be defined by the recurrence relation
F(0) = 0, F(1) = 1,
F(n) = F(n-1) + F(n-2) for n > 1

Fibonacci sequence:  0,   1,  1, 2, 3, 5, 8, 13, 21, 34 ...

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17  F18  F19
 0  1  1  2  3  5  8 13 21 34  55  89 144 233 377 610 987 1597 2584 4181

See 
https://www.geeksforgeeks.org/dsa/introduction-to-dynamic-programming-data-structures-and-algorithm-tutorials/
   for a discussion on various ways to calculate the fibonacci sequence
 
Constraints: 1 <= n <= 45
*/

class Solution : public testing::Test
{
public:
    vector<tuple<int,int,int>> testCases = {
        //  n   NumCombinations    F(n+1)
        // {   1,           1,           1     },
        // {   2,           2,           2     },
        // {   3,           3,           3     },
        // {   4,           5,           5     },
        // {   5,           8,           8     },
        // {   6,          13,          13     },
        {  45,  1836311903,  1836311903     },
    };

    // O(n)
    int fibOrderN(int n)
    {
        if (n <= 1) return n;

        int curr  = 0;
        int prev1 = 1;
        int prev2 = 0;

        for (int i = 2; i <= n; i++)
        {
            curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return curr;
    }

    // O(2^n)
    int fibRecursive(int n)
    {
        if (n <= 1) return n;

        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    
    int climbStairs(int n)
    {
        return fibRecursive(n+1);
        // return fibOrderN(n+1);
    }
};

TEST_F(Solution, NumSteps)
{
    for (auto testCase: testCases)
    {
        int distinctWays = climbStairs(get<0>(testCase));
        cout << "expected: " << get<1>(testCase) << endl;
        cout << "  actual: " << distinctWays << endl;
        EXPECT_EQ(distinctWays, get<1>(testCase));
    }
}


int main(int argc, char** argv)
{
    //Solution s;

    testing::InitGoogleTest(&argc, argv);
    
    int ret = RUN_ALL_TESTS();
    
    return ret;
    
    //return 0;
}