Climbing Stairs to reach at the top.

There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.
 

Consider the example shown in the diagram. The value of n is 3. There are 3 ways to reach the top. The diagram is taken from Easier Fibonacci puzzles

Examples: 

Input: n = 1
Output: 1 There is only one way to climb 1 stair

Input: n=2
Output: 2 There are two ways: (1, 1) and (2)

Input: n = 4
Output: 5 (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)

Climbing Stairs using Recursion:

We can easily find the recursive nature in the above problem. The person can reach n^th stair from either (n-1)^th stair or from (n-2)^th stair. Hence, for each stair n, we try to find out the number of ways to reach n-1^th stair and n-2^th stair and add them to give the answer for the n^th stair. Therefore the Recurrence relation for such an approach comes out to be : 

ways(n) = ways(n-1) + ways(n-2)

The above expression is actually the expression for Fibonacci numbers, but there is one thing to notice, the value of ways(n) is equal to fibonacci(n+1). 

• ways(1) = fib(2) = 1
• ways(2) = fib(3) = 2
• ways(3) = fib(4) = 3

For a better understanding, let’s refer to the recursion tree below:

So we can use the function for Fibonacci numbers to find the value of ways(n).

Below is the implementation of the above approach:

Number of ways = 5

Time Complexity: O(2ⁿ) , because at each stair there are two choices and there are total of n stairs.
Auxiliary Space: O(n), because of recursive stack space.

Climbing Stairs Problem using Dynamic Programming (Memoization) :

The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So a 1D array can be used to store results of previously solved subproblems.

Follow the below steps to Implement the idea:

• Create a 1D dp where dp[i] represent the number of ways to reach the ith stair from the bottom.
• Check if answer for subproblem already exist or not in dp.
• Recursively call for subproblems and store their result in dp (i.e, dp[n] = countWays(n – 1, dp) + countWays(n – 2, dp)).
• Finally, return dp[n], as it will store the answer for input n.

Below is the implementation of the above approach:

Number of ways = 5

Time Complexity: O(n)
Auxiliary Space: O(n)

Climbing Stairs using Dynamic Programming (Tabulation):

Create a table dp[] in bottom up manner using the following relation: 

dp[i] = dp[i-1] + dp[i-2]

Follow the below steps to Implement the idea:

• Create a 1D dp where dp[i] represent the number of ways to reach the ith stair from the bottom.
• Initialise dp[0] = 1, as there is only one way for n = 0 and dp[1] = 2 as there are only 2 ways for input n = 2.
• Now for each i >= 2, dp[i] = dp[i-1]+dp[i-2]

Below code implements the above approach: 

Number of ways = 5

Time Complexity: O(n)
Auxiliary Space: O(n)

Coin change Problem using the Space Optimized approach:

In the above approach it can be seen that dp[i] only depends on previous states. We can optimize the space complexity of the dynamic programming solution to O(1) by using only two variables prev1 and prev2 to keep track of the previous two values of dp[i-1] and dp[i-2]. Since we only need these two values to calculate the next value, we don’t need to store the entire array.

Below is the code implementation of the above idea:

Number of Ways : 5

Time Complexity: O(N)
Auxiliary Space: O(1)

Coin change Problem using Mathematics:

Note: This Method is only applicable for the question Count ways to N’th Stair (Order does not matter) .

Order does not matter means for n = 4  {1 2 1}  ,{2 1 1} , {1 1 2} are considered same.

In this method, simply count the number of sets having 2, which will be equal to n/2. So total number of ways will be n/2+1 (one is added to incude the set which does not contain any 2)

Below is the implementation of above approach:

Number of ways when order of steps does not matter is : 3

Time Complexity : O(1)
Auxiliary Space : O(1)

Coin change Problem using Matrix Exponentiation:

Approach: The number of ways to reach n^th stair (Order matters) is equal to the sum of number of ways to reach (n-1)^th stair and (n-2)^th stair

This corresponds to the following recurrence relation:

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2

where f(n) indicates the number of ways to reach n^th stair

Note: 

f(1) = 1 because there is only 1 way to reach n=1 stair  {1}

f(2) = 2 because there are 2 ways to reach n=2 stairs  {1,1} , {2}

It is a type of linear recurrence relation with constant coefficients and we can solve them using Matrix Exponentiation method which basically finds a transformation matrix for a given recurrence relation and repeatedly applies this transformation to a base vector to arrive at the solution).

F(n) = CN-1F(1)
where
C is the transformation matrix
F(1) is the base vector
F(n) is the desired solution

So, for our case the transformation matrix C would be:

C^N-1 can be calculated using Divide and Conquer technique, in O( (K^3) Log n) where K is dimension of C 

And F(1):

As an example, For n= 4: 

F(4) = C³F(1)

C³ = 

Hence, C³F(1) = 

Number of ways = 5

Time Complexity: O(Log n)
Auxiliary Space: O(1)