/*PROBLEM: You are climbing a stair case. It takes n steps to reach to the top. Each
           time you can either climb 1 or 2 steps. In how many distinct ways can you
           climb to the top?
           NOTE: Given n will be a positive integer.
*/

//RECURSIVE IMPLEMENTATION

long long climbingStairs(long long n)
{
    //base condition(s)
    //if no stairs then only 1 way(already at top)
    if(n==0)
       return 1;

    //take one step to reach the end, and this is the only way
    else if(n==1)
       return 1;

    //take one step twice or take two steps to reach the end
    else if(n==2)
       return 2;

    //choice diagram code
    /*if we take one step, we are left with "n - 1" steps,
      if we take two steps, we are left with "n - 2" steps.
      Now add all the available choices*/
    return climbingStairs(n-1) + climbingStairs(n-2);
}

/*Time Complexity: O(2^n) because we are making 2 recursive calls in the same function.
  Space Complexity: O(n) which is used to store the recursion stack.*/

*********************************************************************************************************

//MEMOIZED IMPLEMENTATION

long long climbingStairs(long long n)
{
    //base condition(s)
    //if no stairs then only 1 way(already at top)
    if(n==0)
       return 1;

    //take one step to reach the end, and this is the only way
    else if(n==1)
       return 1;

    //take one step twice or take two steps to reach the end
    else if(n==2)
       return 2;

    //check if already calculated or not
    else if(dp[n]!=-1)
       return dp[n];

    //choice diagram code
    /*if we take one step, we are left with "n - 1" steps,
      if we take two steps, we are left with "n - 2" steps.
      Now add all the available choices*/
    return dp[n]=climbingStairs(n-1) + climbingStairs(n-2);
}

//dp[] is a 1 D global matrix/vector, with size (n+1) and initialized
//with -1, memset(dp, -1, sizeof(dp));

/*Time Complexity: O(n) because memoization array dp[n+1] stores the results of all
  sub-problems. We can conclude that we will not have more than n + 1 sub-problems.
  Space Complexity: O(n) which is used to store the dp[] array.
*/

*********************************************************************************************************

//TABULATION IMPLEMENTATION (Real DP ;))

long long climbingStairs(long long n)
{
    //initialisation of dp vector
    dp[0]=1; dp[1]=1; dp[2]=2;

    //choice diagram code iterative version
    for(long long i=3; i<(n+1); i++)
       dp[i]=dp[i-1]+dp[i-2];

    return dp[n];
}

//dp[] is a 1 D global matrix/vector, with size (n+1)
/*Time Complexity: O(n)
  Space Complexity: O(n) which is used to store the dp[] array.
*/

*********************************************************************************************************

//MEMORY OPTIMIZED IMPLEMENTATION
/*As we can see from the visualization of the recursive stack and other solutions,
  to be able to calculate the n, you need the value of last two combinations: n-1
  and n-2.
  These two values are enough and we don’t need to store all other past combinations.
*/

long long climbingStairs(long long n)
{
    //base condition(s)
    //if no stairs then only 1 way(already at top)
    if(n==0)
       return 1;

    //take one step to reach the end, and this is the only way
    else if(n==1)
       return 1;

    //take one step twice or take two steps to reach the end
    else if(n==2)
       return 2;

    long long first=1, second=2, third;
    for(long long i=3; i<(n+1); i++)
    {
       third=second+first;
       first=second;
       second=third;
    }

    return third;
}

//Time Complexity: O(n)
//Space Complexity: O(1)