How many ways can you climb a staircase with 10 steps if you can take either 1 or 2 steps at a time hint group the different ways according to the number of double steps?

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach 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)

Method 1: The first method uses the technique of recursion to solve this problem.
Approach: We can easily find the recursive nature in the above problem. The person can reach nth 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-1th stair and n-2th stair and add them to give the answer for the nth stair. Therefore the expression 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 -:

Input: N = 4 fib(5) '3' / \ '2' / \ fib(4) fib(3) '2' / \ '1' / \ / \ / \ fib(3) fib(2)fib(2) fib(1) / \ '1' / \ '0' '1' / '1'\ / \ / \ fib(1) fib(0) fib(2) fib(1)

So we can use the function for Fibonacci numbers to find the value of ways(n). Following is C++ implementation of the above idea.

#include <bits/stdc++.h>
using namespace std;
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
int countWays(int s)
{
    return fib(s + 1);
}
int main()
{
    int s = 4;
    cout << "Number of ways = " << countWays(s);
    return 0;
}

#include <stdio.h>
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
int countWays(int s)
{
    return fib(s + 1);
}
int main()
{
    int s = 4;
    printf("Number of ways = %d", countWays(s));
    getchar();
    return 0;
}

class stairs {
    static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
    static int countWays(int s)
    {
        return fib(s + 1);
    }
    public static void main(String args[])
    {
        int s = 4;
        System.out.println("Number of ways = " + countWays(s));
    }
} 

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
def countWays(s):
    return fib(s + 1)
s = 4
print "Number of ways = ",
print countWays(s)

using System;
class GFG {
    static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
    static int countWays(int s)
    {
        return fib(s + 1);
    }
    static public void Main()
    {
        int s = 4;
        Console.WriteLine("Number of ways = " + countWays(s));
    }
}

<?php
function fib($n)
{
if ($n <= 1)
    return $n;
return fib($n - 1) +
       fib($n - 2);
}
function countWays($s)
{
    return fib($s + 1);
}
$s = 4;
echo "Number of ways = ",
           countWays($s);
?>

<script>
function fib(n)
{
if (n <= 1)
    return n;
return fib(n - 1) +
       fib(n - 2);
}
function countWays(s)
{
    return fib(s + 1);
}
let s = 4;
document.write("Number of ways = " + countWays(s));
</script>

Complexity Analysis:

Time Complexity: O(2^n)
The time complexity of the above implementation is exponential (golden ratio raised to power n) due to redundant calculations.It can be optimized to work in O(Logn) time using the previously discussed Fibonacci function optimizations.
Auxiliary Space: O(1)

Generalization of the Problem
How to count the number of ways if the person can climb up to m stairs for a given value m. For example, if m is 4, the person can climb 1 stair or 2 stairs or 3 stairs or 4 stairs at a time.

Approach: For the generalization of above approach the following recursive relation can be used.

ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... ways(n-m, m)

In this approach to reach nth stair, try climbing all possible number of stairs lesser than equal to n from present stair.

Following is the implementation of above recurrence.

#include <bits/stdc++.h>
using namespace std;
int countWaysUtil(int n, int m)
{
    if (n <= 1)
    {
        return n;
    }
    int res = 0;
    for(int i = 1; i <= m && i <= n; i++)
    {
       res += countWaysUtil(n - i, m);
    }
    return res;
}
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}
int main()
{
    int s = 4, m = 2;
    cout << "Number of ways = " << countWays(s, m);
    return 0;
}

#include <stdio.h>
int countWaysUtil(int n, int m)
{
    if (n <= 1)
        return n;
    int res = 0;
    for (int i = 1; i <= m && i <= n; i++)
        res += countWaysUtil(n - i, m);
    return res;
}
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}
int main()
{
    int s = 4, m = 2;
    printf("Number of ways = %d", countWays(s, m));
    return 0;
}

class stairs {
    static int countWaysUtil(int n, int m)
    {
        if (n <= 1)
            return n;
        int res = 0;
        for (int i = 1; i <= m && i <= n; i++)
            res += countWaysUtil(n - i, m);
        return res;
    }
    static int countWays(int s, int m)
    {
        return countWaysUtil(s + 1, m);
    }
    public static void main(String args[])
    {
        int s = 4, m = 2;
        System.out.println("Number of ways = "
                           + countWays(s, m));
    }
} 

def countWaysUtil(n, m):
    if n <= 1:
        return n
    res = 0
    i = 1
    while i<= m and i<= n:
        res = res + countWaysUtil(n-i, m)
        i = i + 1
    return res
def countWays(s, m):
    return countWaysUtil(s + 1, m)
s, m = 4, 2
print "Number of ways =", countWays(s, m)

using System;
public class stairs
{
    static int countWaysUtil(int n, int m)
    {
        if (n <= 1)
            return n;
        int res = 0;
        for (int i = 1; i <= m && i <= n; i++)
            res += countWaysUtil(n - i, m);
        return res;
    }
    static int countWays(int s, int m)
    {
        return countWaysUtil(s + 1, m);
    }
    public static void Main(String []args)
    {
        int s = 4, m = 2;
        Console.WriteLine("Number of ways = "
                           + countWays(s, m));
    }
}

<?php
function countWaysUtil($n, $m)
{
    if ($n <= 1)
        return $n;
    $res = 0;
    for ($i = 1; $i <= $m &&
                 $i <= $n; $i++)
        $res += countWaysUtil($n - $i, $m);
    return $res;
}
function countWays($s, $m)
{
    return countWaysUtil($s + 1, $m);
}
$s = 4; $m = 2;
echo "Number of ways = ",
      countWays($s, $m);
?>

<script>
function countWaysUtil(n, m)
{
    if (n <= 1)
        return n;
    let res = 0;
    for (let i = 1; i <= m &&
                 i <= n; i++)
        res += countWaysUtil(n - i, m);
    return res;
}
function countWays(s, m)
{
    return countWaysUtil(s + 1, m);
}
let s = 4;
let m = 2;
document.write("Number of ways = " + countWays(s, m));
</script>

Complexity Analysis:

Time Complexity: O(2^n)
The time complexity of the above implementation is exponential (golden ratio raised to power n) due to redundant calculations. It can be optimized to O(m*n) by using dynamic programming.
Auxiliary Space: O(1)

Method 2: Memoization

We can use the bottom-up approach of dp to solve this problem as well

For this, we can create an array dp[] and initialize it with -1.

Whenever we see that a subproblem is not solved we can call the recursive method,

else we stop the recursion if that the subproblem is solved already.

#include <bits/stdc++.h>
using namespace std;
int fib(int n, int dp[])
{
    if (n <= 1)
        return dp[n] = 1;
    if (dp[n] != -1) {
        return dp[n];
    }
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
    return dp[n];
}
int countWays(int n)
{
    int dp[n + 1];
    memset(dp, -1, sizeof dp);
    fib(n, dp);
    return dp[n];
}
int main()
{
    int n = 4;
    cout << "Number of ways = " << countWays(n);
    return 0;
}

#include <stdio.h>
#include <string.h>
int fib(int n, int dp[])
{
    if (n <= 1)
        return dp[n] = 1;
    if (dp[n] != -1) {
        return dp[n];
    }
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
    return dp[n];
}
int countWays(int n)
{
    int dp[n + 1];
    memset(dp, -1, sizeof dp);
    fib(n, dp);
    return dp[n];
}
int main()
{
    int n = 4;
    printf("Number of ways = %d", countWays(n));
    return 0;
}

class GFG
{
  static int fib(int n, int dp[])
  {
    if (n <= 1)
      return dp[n] = 1;
    if (dp[n] != -1) {
      return dp[n];
    }
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
    return dp[n];
  }
  static int countWays(int n)
  {
    int[] dp = new int[n + 1];
    for (int i = 0; i < n + 1; i++) {
      dp[i] = -1;
    }
    fib(n, dp);
    return dp[n];
  }
  public static void main(String[] args)
  {
    int n = 4;
    System.out.println(countWays(n));
  }
}

def fib(n, dp):
    if (n <= 1):
        return 1
    if(dp[n] != -1 ):
        return dp[n]
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp)
    return  dp[n]
def countWays(n):
    dp = [-1 for i in range(n + 1)]
    fib(n, dp)
    return dp[n]
n = 4
print("Number of ways = " + str(countWays(n)))

using System;
class GFG
{
  static int fib(int n, int[] dp)
  {
    if (n <= 1)
      return dp[n] = 1;
    if (dp[n] != -1) {
      return dp[n];
    }
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
    return dp[n];
  }
  static int countWays(int n)
  {
    int[] dp = new int[n + 1];
    for (int i = 0; i < n + 1; i++) {
      dp[i] = -1;
    }
    fib(n, dp);
    return dp[n];
  }
public static void Main()
{
    int n = 4;
    Console.Write("Number of ways = " + countWays(n));
}
}

<script>
function fib(n, dp)
{
    if (n <= 1)
        return dp[n] = 1;
    if(dp[n] != -1 ){
        return dp[n] ;
    }
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
    return  dp[n] ;
}
function countWays(n)
{
    let dp = new Array(n+1).fill(-1) ;
    fib(n, dp) ;
    return dp[n] ;
}
let n = 4;
document.write("Number of ways = " + countWays(n));
</script>

Complexity Analysis:

Time Complexity: O(n)

Auxiliary Space: O(n)

Method 3: This method uses the technique of Dynamic Programming to arrive at the solution.

Approach: We create a table res[] in bottom up manner using the following relation:

res[i] = res[i] + res[i-j] for every (i-j) >= 0

such that the ith index of the array will contain the number of ways required to reach the ith step considering all the possibilities of climbing (i.e. from 1 to i).

Below code implements the above approach:

#include <iostream>
using namespace std;
int countWaysUtil(int n, int m)
{
    int res[n];
    res[0] = 1;
    res[1] = 1;
    for(int i = 2; i < n; i++)
    {
       res[i] = 0;
       for(int j = 1; j <= m && j <= i; j++)
          res[i] += res[i - j];
    }
    return res[n - 1];
}
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}
int main()
{
    int s = 4, m = 2;
    cout << "Number of ways = "
         << countWays(s, m);
    return 0;
}

#include <stdio.h>
int countWaysUtil(int n, int m)
{
    int res[n];
    res[0] = 1;
    res[1] = 1;
    for (int i = 2; i < n; i++) {
        res[i] = 0;
        for (int j = 1; j <= m && j <= i; j++)
            res[i] += res[i - j];
    }
    return res[n - 1];
}
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}
int main()
{
    int s = 4, m = 2;
    printf("Number of ways = %d", countWays(s, m));
    return 0;
}

class GFG {
    static int countWaysUtil(int n, int m)
    {
        int res[] = new int[n];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n; i++) {
            res[i] = 0;
            for (int j = 1; j <= m && j <= i; j++)
                res[i] += res[i - j];
        }
        return res[n - 1];
    }
    static int countWays(int s, int m)
    {
        return countWaysUtil(s + 1, m);
    }
    public static void main(String[] args)
    {
        int s = 4, m = 2;
        System.out.println("Number of ways = "
                           + countWays(s, m));
    }
}

def countWaysUtil(n, m):
    res = [0 for x in range(n)]
    res[0], res[1] = 1, 1
    for i in range(2, n):
        j = 1
        while j<= m and j<= i:
            res[i] = res[i] + res[i-j]
            j = j + 1
    return res[n-1]
def countWays(s, m):
    return countWaysUtil(s + 1, m)
s, m = 4, 2
print "Number of ways =", countWays(s, m)

using System;
class GFG {
    static int countWaysUtil(int n, int m)
    {
        int[] res = new int[n];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n; i++) {
            res[i] = 0;
            for (int j = 1; j <= m && j <= i; j++)
                res[i] += res[i - j];
        }
        return res[n - 1];
    }
    static int countWays(int s, int m)
    {
        return countWaysUtil(s + 1, m);
    }
    public static void Main()
    {
        int s = 4, m = 2;
        Console.WriteLine("Number of ways = "
                          + countWays(s, m));
    }
}

<?php
function countWaysUtil($n, $m)
{
    $res[0] = 1; $res[1] = 1;
    for ($i = 2; $i < $n; $i++)
    {
        $res[$i] = 0;
        for ($j = 1; $j <= $m && $j <= $i; $j++)
        $res[$i] += $res[$i - $j];
    }
    return $res[$n - 1];
}
function countWays($s, $m)
{
    return countWaysUtil($s + 1, $m);
}
    $s = 4;
    $m = 2;
    echo "Number of ways = ", countWays($s, $m);
?>

<script>



function countWaysUtil(n, m)
{
    let res = [];
    res[0] = 1;
    res[1] = 1;
    for (let i = 2; i < n; i++)
    {
        res[i] = 0;
        for (let j = 1; j <= m && j <= i; j++)
        res[i] += res[i - j];
    }
    return res[n - 1];
}
function countWays(s, m)
{
    return countWaysUtil(s + 1, m);
}
    let s = 4;
    let m = 2;
    document.write("Number of ways = " + countWays(s, m));
</script>

Complexity Analysis:

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

Method 4: This method uses the Dynamic Programming Approach with the Space Optimization

Approach: In this Method, we can just optimize the Tabular Approach of Dynamic Programming by not using any extra space.

First, we can create two variables prev and prev2 to store the ways to climb one stair or two stairs.

Then we can run a for loop to count the total number of ways to reach the top.

Below is the code implementation of the Above idea:

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int countWays(int n)
{
    int prev = 1;
    int prev2 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev + prev2;
        prev2 = prev;
        prev = curr;
    }
    return prev;
}
int main()
{
    int n = 4;
    cout << "Number of Ways : " << countWays(n);
    return 0;
}

public class Solution {
    static int countWays(int n)
    {
        int prev = 1;
        int prev2 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev + prev2;
            prev2 = prev;
            prev = curr;
        }
        return prev;
    }
    public static void main(String[] args)
    {
        int n = 4;
        System.out.println("Number of Ways : "
                           + countWays(n));
    }
}

using System;
public class GFG {
    public static int countWays(int n)
    {
        int prev = 1;
        int prev2 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev + prev2;
            prev2 = prev;
            prev = curr;
        }
        return prev;
    }
    public static void Main(string[] args)
    {
        int n = 4;
        Console.WriteLine("Number of Ways : "
                          + countWays(n));
    }
}

output:

given n=4

Number of ways: 5

Complexity Analysis :

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

Method 5: The third method uses the technique of Sliding Window to arrive at the solution.
Approach: This method efficiently implements the above Dynamic Programming approach.
In this approach for the ith stair, we keep a window of sum of last m possible stairs from which we can climb to the ith stair. Instead of running an inner loop, we maintain the result of the inner loop in a temporary variable. We remove the elements of the previous window and add the element of the current window and update the sum.

Below code implements the above idea

#include <iostream>
using namespace std;
int countWays(int n, int m)
{
    int res[n + 1];
    int temp = 0;
    res[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int s = i - m - 1;
        int e = i - 1;
        if (s >= 0)
        {
            temp -= res[s];
        }
        temp += res[e];
        res[i] = temp;
    }
    return res[n];
}
int main()
{
    int n = 5, m = 3;
    cout << "Number of ways = "
         << countWays(n, m);
    return 0;
}

#include <stdio.h>
int countWays(int n, int m)
{
    int res[n + 1];
    int temp = 0;
    res[0] = 1;
    for (int i = 1; i <= n; i++) {
        int s = i - m - 1;
        int e = i - 1;
        if (s >= 0) {
            temp -= res[s];
        }
        temp += res[e];
        res[i] = temp;
    }
    return res[n];
}
int main()
{
    int n = 5, m = 3;
    printf("Number of ways = %d",
           countWays(n, m));
    return 0;
}

class GFG{
static int countWays(int n, int m)
{
    int res[] = new int[n + 1];
    int temp = 0;
    res[0] = 1;
    for(int i = 1; i <= n; i++)
    {
       int s = i - m - 1;
       int e = i - 1;
       if (s >= 0)
       {
           temp -= res[s];
       }
       temp += res[e];
       res[i] = temp;
    }
    return res[n];
}
public static void main(String[] args)
{
    int n = 5, m = 3;
    System.out.println("Number of ways = " +
                       countWays(n, m));
}
}

def countWays(n, m):
    temp = 0
    res = [1]
    for i in range(1, n + 1):
        s = i - m - 1
        e = i - 1
        if (s >= 0):
            temp -= res[s]
        temp += res[e]
        res.append(temp)
    return res[n]
n = 5
m = 3
print('Number of ways =', countWays(n, m))

using System;
class GFG{
static int countWays(int n, int m)
{
    int[] res = new int[n + 1];
    int temp = 0;
    res[0] = 1;
    for(int i = 1; i <= n; i++)
    {
       int s = i - m - 1;
       int e = i - 1;
       if (s >= 0)
       {
           temp -= res[s];
       }
       temp += res[e];
       res[i] = temp;
    }
    return res[n];
}
public static void Main()
{
    int n = 5, m = 3;
    Console.WriteLine("Number of ways = " +
                      countWays(n, m));
}
}

<script>
    function countWays(n , m)
    {
        var res = Array(n + 1).fill(0);
        var temp = 0;
        res[0] = 1;
        for (i = 1; i <= n; i++) {
            var s = i - m - 1;
            var e = i - 1;
            if (s >= 0) {
                temp -= res[s];
            }
            temp += res[e];
            res[i] = temp;
        }
        return res[n];
    }
        var n = 5, m = 3;
        document.write("Number of ways = " +
        countWays(n, m));
</script>

OutputNumber of ways = 13

Complexity Analysis:

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

This article is contributed by Abhishek. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Method 6: The fourth method uses simple mathematics but this is only applicable for this problem if (Order does not matter) while counting steps.

Approach: In This method we simply count the number of sets having 2.

#include <iostream>
using namespace std;
int main() {
    int n;
    n=5;
    cout<<"Number of ways when order of steps does not matter is : "<<1+(n/2)<<endl;   
    return 0;
}

import java.util.*;
class GFG{
public static void main(String[] args)
{
    int n;
    n = 5;
    System.out.print("Number of ways when order of steps " +
                     "does not matter is : " + (1 + (n / 2)));
}
}

n = 5

print("Number of ways when order "

"of steps does not matter is : ", 1 + (n // 2))

using System;
class GFG{
static public void Main()
{
    int n;
    n = 5;
    Console.WriteLine("Number of ways when order of steps " +
                      "does not matter is : " + (1 + (n / 2)));
}
}

<script>
var n;
n = 5;
document.write("Number of ways when order " +
               "of steps does not matter is : ",
               parseInt(1 + (n / 2)));   
</script>

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

Complexity Analysis:

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

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.

Method 6: This method uses the technique of Matrix Exponentiation to arrive at the solution.

Approach: The number of ways to reach nth 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 nth 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:

CN-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) = C3F(1)

C3 =

Hence, C3F(1) =

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LOOP(i, n) for (int i = 1; i < n; i++)
matrix mul(matrix A, matrix B, long long MOD = 1000000007)
{
    int K = A.size();
    matrix C(K, vector<long long>(K, 0));
    LOOP(i, K)
        LOOP(j, K)
            LOOP(k, K)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
matrix power(matrix A, long long n)
{
    if (n == 1)
        return A;
    if (n % 2 != 0) {
        A = mul(A, power(A, n - 1));
    }
    else {
        A = power(A, n / 2);
        A = mul(A, A);
    }
    return A;
}
long long ways(int n)
{
    vector<long long> F(3);
    F[1] = 1;
    F[2] = 2;
    int K = 2;
    long long MOD = 1000000007;
    matrix C(K + 1, vector<long long>(K + 1, 0));
    for (int i = 1; i < K; ++i) {
        C[i][i + 1] = 1;
    }
    C[K][1] = 1;
    C[K][2] = 1;
    if (n <= 2)
        return F[n];
    C = power(C, n - 1);
    long long result = 0;
    for (int i = 1; i <= K; ++i) {
        result = (result + C[1][i] * F[i]) % MOD;
    }
    return result;
}
int main()
{
    int n = 4;
    cout << "Number of ways = " << ways(n) << endl;
}

import java.util.*;
class GFG
{
    static long[][] mul(long[][] A, long[][] B, long MOD) {
        int K = A.length;
        long[][] C = new long[K][K];
        for (int i = 1; i < K; i++)
            for (int j = 1; j < K; j++)
                for (int k = 1; k < K; k++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    }
    static long[][] power(long[][] A, long n) {
        if (n == 1)
            return A;
        if (n % 2 != 0)
        {
            A = mul(A, power(A, n - 1), 1000000007);
        }
      else
      {
            A = power(A, n / 2);
            A = mul(A, A, 1000000007);
        }
        return A;
    }
    static long ways(int n) {
        long[] F = new long[3];
        F[1] = 1;
        F[2] = 2;
        int K = 2;
        long MOD = 1000000007;
        long[][] C = new long[K + 1][K + 1];
        for (int i = 1; i < K; ++i) {
            C[i][i + 1] = 1;
        }
        C[K][1] = 1;
        C[K][2] = 1;
        if (n <= 2)
            return F[n];
        C = power(C, n - 1);
        long result = 0;
        for (int i = 1; i <= K; ++i) {
            result = (result + C[1][i] * F[i]) % MOD;
        }
        return result;
    }
    public static void main(String[] args) {
        int n = 4;
        System.out.print("Number of ways = " + ways(n) + "\n");
    }
}

def mul(A, B, MOD):
    K = len(A);
    C = [[0 for i in range(K)] for j in range(K)] ;
    for i in range(1, K):
        for j in range(1, K):
            for k in range(1, K):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
def power( A,  n):
    if (n == 1):
        return A;
    if (n % 2 != 0):
        A = mul(A, power(A, n - 1), 1000000007);
    else:
        A = power(A, n // 2);
        A = mul(A, A, 1000000007);
    return A;
def ways(n):
    F = [0 for i in range(3)];
    F[1] = 1;
    F[2] = 2;
    K = 2;
    MOD = 1000000007;
    C = [[0 for i in range(K+1)] for j in range(K+1)];
    for i in range(1,K):
        C[i][i + 1] = 1;
    C[K][1] = 1;
    C[K][2] = 1;
    if (n <= 2):
        return F[n];
    C = power(C, n - 1);
    result = 0;
    for i in range(1,K+1):
        result = (result + C[1][i] * F[i]) % MOD;
    return result;
if __name__ == '__main__':
    n = 4;
    print("Number of ways = " , ways(n) , "");

using System;
public class GFG {
    static long[,] mul(long[,] A, long[,] B, long MOD) {
        int K = A.GetLength(0);
        long[,] C = new long[K,K];
        for (int i = 1; i < K; i++)
            for (int j = 1; j < K; j++)
                for (int k = 1; k < K; k++)
                    C[i,j] = (C[i,j] + A[i,k] * B[k,j]) % MOD;
        return C;
    }
    static long[,] power(long[,] A, long n) {
        if (n == 1)
            return A;
        if (n % 2 != 0) {
            A = mul(A, power(A, n - 1), 1000000007);
        } else {
            A = power(A, n / 2);
            A = mul(A, A, 1000000007);
        }
        return A;
    }
    static long ways(int n) {
        long[] F = new long[3];
        F[1] = 1;
        F[2] = 2;
        int K = 2;
        long MOD = 1000000007;
        long[,] C = new long[K + 1,K + 1];
        for (int i = 1; i < K; ++i) {
            C[i,i + 1] = 1;
        }
        C[K,1] = 1;
        C[K,2] = 1;
        if (n <= 2)
            return F[n];
        C = power(C, n - 1);
        long result = 0;
        for (int i = 1; i <= K; ++i) {
            result = (result + C[1,i] * F[i]) % MOD;
        }
        return result;
    }
    public static void Main(String[] args) {
        int n = 4;
        Console.Write("Number of ways = " + ways(n) + "\n");
    }
}

<script>
     function mul( A,  B , MOD) {
        var K = A.length;
        var C = Array(K).fill().map(()=>Array(K).fill(0));
        for (var i = 1; i < K; i++)
            for (var j = 1; j < K; j++)
                for (var k = 1; k < K; k++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    }
     function power( A , n) {
        if (n == 1)
            return A;
        if (n % 2 != 0) {
            A = mul(A, power(A, n - 1), 1000000007);
        } else {
            A = power(A, n / 2);
            A = mul(A, A, 1000000007);
        }
        return A;
    }
    function ways(n) {
        var F = Array(3).fill(0);
        F[1] = 1;
        F[2] = 2;
        var K = 2;
        var MOD = 1000000007;
    var  C = Array(K+1).fill().map(()=>Array(K+1).fill(0));
        for (var i = 1; i < K; ++i) {
            C[i][i + 1] = 1;
        }
        C[K][1] = 1;
        C[K][2] = 1;
        if (n <= 2)
            return F[n];
        C = power(C, n - 1);
        var result = 0;
        for (var i = 1; i <= K; ++i) {
            result = (result + C[1][i] * F[i]) % MOD;
        }
        return result;
    }
        var n = 4;
        document.write("Number of ways = " + ways(n) + "\n");
</script>

Complexity Analysis:

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

Generalization of the Problem:

Given an array A {a1, a2, …., am} containing all valid steps, compute the number of ways to reach nth stair. (Order does matter)

Examples:

Input: A = [1,2] n = 4 Output: 5 Explanation: This is the given problem, i.e, count the number of ways to reach n=4 stairs with climbing 1 or 2 stairs at a time Therefore, ways will be: {1,1,1,1} {1,1,2} {1,2,1} {2,1,1} {2,2} = 5 Input: A = [2,4,5] n = 9 Output: 5 Explanation: There are 5 ways to reach n=9 stairs with climbing 2 or 4 or 5 stairs at a time Therefore, ways will be: {5,4} {4,5} {2,2,5} {2,5,2} {5,2,2} = 5

Approach:

The number of ways to reach nth stair is given by the following recurrence relation

Let K be the largest element in A.

Step1: Calculate base vector F(1) ( consisting of f(1) …. f(K) )

It can be done in O(m2K) time using dynamic programming approach as follows:

Let’s take A = {2,4,5} as an example. To calculate F(1) = { f(1), f(2), f(3), f(4), f(5) } we will maintain an initially empty array and iteratively append Ai to it and for each Ai we will find the number of ways to reach [Ai-1, to Ai,]

Hence for A = {2 ,4 ,5}

Let T be the initially empty array

Iteration 1: T = {2} n = {1,2} dp = {0,1} (Number of ways to reach n=1,2 with steps given by T) Iteration 2: T = {2,4} n = {1,2,3,4} dp = {0,1,0,2} (Number of ways to reach n=1,2,3,4 with steps given by T) Iteration 3: T = {2,4,5} n = {1,2,3,4,5} dp = {0,1,0,2,1} (Number of ways to reach n=1,2,3,4,5 with steps given by T)

Note: Since some values are already calculated (1,2 for Iteration 2, etc.) we can avoid them in loop

After all iterations, the dp array would be: [0,1,0,2,1]

Thus, base vector F(1) for A = [2,4,5] is:

Now that we have the base vector F(1), calculation of C (Transformation matrix) is easy

Step 2: Calculate C, the transformation matrix

It is a matrix having elements Ai,i+1= 1 and last row contains constants

Now constants can be determined by the presence of that element in A

So for A = [2,4,5] constants will be c = [1,1,0,1,0] (Ci = 1 if (K-i+1) is present in A, or else 0 where 1 <= i <= K )

Thus, Transformation matrix C for A =[2,4,5] is:

0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1
1	1	0	1	0

Step 3: Calculate F(n)

To calculate F(n), following formula is used:

F(n) = Cn-1F(1)

Now that we have C and F(1) we can use Divide and Conquer technique to find Cn-1 and hence the desired output

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LOOP(i, n) for (int i = 1; i < n; i++)
matrix mul(matrix A, matrix B, long long MOD = 1000000007)
{
    int K = A.size();
    matrix C(K, vector<long long>(K, 0));
    LOOP(i, K)
        LOOP(j, K)
            LOOP(k, K)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
matrix power(matrix A, long long n)
{
    if (n == 1)
        return A;
    if (n % 2 != 0) {
        A = mul(A, power(A, n - 1));
    }



    else {
        A = power(A, n / 2);
        A = mul(A, A);
    }
    return A;
}
vector<long long> initialize(vector<long long> A)
{
    int K = A[A.size() - 1]; 
    vector<long long> F(K + 1, 0);
    vector<long long> dp(K + 1);
    dp[0] = 0;
    dp[A[1]] = 1; 
    F[A[1]] = 1;
    for (int i = 2; i < A.size(); ++i) {
        for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
            for (int k = 1; k < i; ++k) {
                dp[j] += dp[j - A[k]];
            }
        }
        dp[A[i]] += 1;
        F[A[i]] = dp[A[i]];
    }
    return F;
}
long long ways(vector<long long> A, int n)
{
    int K = A[A.size() - 1]; 
    vector<long long> F = initialize(A); 
    int MOD = 1000000007;
    matrix C(K + 1, vector<long long>(K + 1, 0));
    for (int i = 1; i < K; ++i) {
        C[i][i + 1] = 1;
    }
    for (int i = 1; i < A.size(); ++i) {
        C[K][K - A[i] + 1] = 1;
    }
    if (n <= K)
        return F[n];
    C = power(C, n - 1); 
    long long result = 0;
    for (int i = 1; i <= K; ++i) {
        result = (result + C[1][i] * F[i]) % MOD;
    }
    return result;
}
int main()
{
    int n = 9;
    vector<long long> A = {
        0, 2, 4, 5
    }; 
    cout << "Number of ways = " << ways(A, n) << endl;
}

import java.util.*;
class GFG{
  static int[][] mul(int[][] A, int[][] B,int MOD)
  {
    int K = A.length;
    int[][] C = new int[K][K];
    for (int i = 1; i < K; i++)
      for (int j = 1; j < K; j++)
        for (int k = 1; k < K; k++)
          C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
  }
  static int[][] power(int[][] A, long n)
  {
    if (n == 1)
      return A;
    if (n % 2 != 0)
    {
      A = mul(A, power(A, n - 1), 1000000007);
    }
    else {
      A = power(A, n / 2);
      A = mul(A, A, 1000000007);
    }
    return A;
  }
  static int[] initialize(int[] A)
  {
    int K = A[A.length - 1]; 
    int[] F = new int[K+1];
    int[] dp = new int[K+1];
    dp[0] = 0;
    dp[A[1]] = 1; 
    F[A[1]] = 1;
    for (int i = 2; i < A.length; ++i)
    {
      for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
        for (int k = 1; k < i; ++k) {
          dp[j] += dp[j - A[k]];
        }
      }
      dp[A[i]] += 1;
      F[A[i]] = dp[A[i]];
    }
    return F;
  }
  static int ways(int[] A, int n)
  {
    int K = A[A.length - 1]; 
    int[] F = initialize(A); 
    int MOD = 1000000007;
    int[][] C = new int[K + 1][K + 1];
    for (int i = 1; i < K; ++i) {
      C[i][i + 1] = 1;
    }
    for (int i = 1; i < A.length; ++i) {
      C[K][K - A[i] + 1] = 1;
    }
    if (n <= K)
      return F[n];
    C = power(C, n - 1); 
    int result = 0;
    for (int i = 1; i <= K; ++i) {
      result = (result + C[1][i] * F[i]) % MOD;
    }
    return result;
  }
  public static void main(String[] args)
  {
    int n = 9;
    int[] A = {0, 2, 4, 5};
    System.out.print("Number of ways = " +  ways(A, n) +"\n");
  }
}

def mul(A, B, MOD):
    K = len(A);
    C = [[0 for i in range(K)] for j in range(K)] ;
    for i in range(1, K):
        for j in range(1, K):
            for k in range(1, K):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
def power(A, n):
    if (n == 1):
        return A;
    if (n % 2 != 0):
        A = mul(A, power(A, n - 1), 1000000007);
    else:
        A = power(A, n // 2);
        A = mul(A, A, 1000000007);
    return A;
def initialize(A):
    K = A[len(A)-1]; 
    F = [0 for i in range(K+1)];
    dp = [0 for i in range(K+1)];
    dp[0] = 0;
    dp[A[1]] = 1; 
    F[A[1]] = 1;
    for i in range(2,len(A)):
        for j in range(A[i - 1] + 1,A[i]+1):
            for k in range(1,i):
                dp[j] += dp[j - A[k]];
        dp[A[i]] += 1;
        F[A[i]] = dp[A[i]];
    return F;
def ways(A, n):
    K = A[len(A) - 1]; 
    F = initialize(A); 
    MOD = 1000000007;
    C = [[0 for i in range(K+1)] for j in range(K+1)];
    for i in range(1,K):
        C[i][i + 1] = 1;
    for i in range(1, len(A)):
        C[K][K - A[i] + 1] = 1;
    if (n <= K):
        return F[n];
    C = power(C, n - 1); 
    result = 0;
    for i in range(1, K+1):
        result = (result + C[1][i] * F[i]) % MOD;
    return result;
if __name__ == '__main__':
    n = 9;
    A = [ 0, 2, 4, 5] ;
    print("Number of ways = " ,ways(A, n));

using System;
public class GFG {
    static int[,] mul(int[,] A, int[,] B, int MOD) {
        int K = A.GetLength(0);
        int[,] C = new int[K,K];
        for (int i = 1; i < K; i++)
            for (int j = 1; j < K; j++)
                for (int k = 1; k < K; k++)
                    C[i,j] = (C[i,j] + A[i,k] * B[k,j]) % MOD;
        return C;
    }
    static int[,] power(int[,] A, long n) {
        if (n == 1)
            return A;
        if (n % 2 != 0) {
            A = mul(A, power(A, n - 1), 1000000007);
        } else {
            A = power(A, n / 2);
            A = mul(A, A, 1000000007);
        }
        return A;
    }
    static int[] initialize(int[] A) {
        int K = A[A.Length - 1]; 
        int[] F = new int[K + 1];
        int[] dp = new int[K + 1];
        dp[0] = 0;
        dp[A[1]] = 1; 
        F[A[1]] = 1;
        for (int i = 2; i < A.Length; ++i) {
            for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
                for (int k = 1; k < i; ++k) {
                    dp[j] += dp[j - A[k]];
                }
            }
            dp[A[i]] += 1;
            F[A[i]] = dp[A[i]];
        }
        return F;
    }
    static int ways(int[] A, int n) {
        int K = A[A.Length - 1]; 
        int[] F = initialize(A); 
        int MOD = 1000000007;
        int[,] C = new int[K + 1,K + 1];
        for (int i = 1; i < K; ++i) {
            C[i,i + 1] = 1;
        }
        for (int i = 1; i < A.GetLength(0); ++i) {
            C[K,K - A[i] + 1] = 1;
        }
        if (n <= K)
            return F[n];
        C = power(C, n - 1); 
        int result = 0;
        for (int i = 1; i <= K; ++i) {
            result = (result + C[1,i] * F[i]) % MOD;
        }
        return result;
    }
    public static void Main(String[] args) {
        int n = 9;
        int[] A = { 0, 2, 4, 5 };
        Console.Write("Number of ways = " + ways(A, n) + "\n");
    }
}

<script>
     function mul(A,  B , MOD) {
        var K = A.length;
        var  C = Array(K).fill().map(()=>Array(K).fill(0));
        for (var i = 1; i < K; i++)
            for (var j = 1; j < K; j++)
                for (var k = 1; k < K; k++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    }
     function power(A , n) {
        if (n == 1)
            return A;
        if (n % 2 != 0) {
            A = mul(A, power(A, n - 1), 1000000007);
        } else {
            A = power(A, parseInt(n / 2));
            A = mul(A, A, 1000000007);
        }
        return A;
    }
     function initialize(A) {
        var K = A[A.length - 1]; 
        var F = Array(K+1).fill(0);
        var dp = Array(K+1).fill(0);
        dp[0] = 0;
        dp[A[1]] = 1; 
        F[A[1]] = 1;
        for (var i = 2; i < A.length; ++i) {
            for (var j = A[i - 1] + 1; j <= A[i]; ++j) {
                for (var k = 1; k < i; ++k) {
                    dp[j] += dp[j - A[k]];
                }
            }
            dp[A[i]] += 1;
            F[A[i]] = dp[A[i]];
        }
        return F;
    }
    function ways(A , n) {
        var K = A[A.length - 1]; 
        var F = initialize(A); 
        var MOD = 1000000007;
        var C = Array(K+1).fill().map(()=>Array(K+1).fill(0));
        for (var i = 1; i < K; ++i) {
            C[i][i + 1] = 1;
        }
        for (var i = 1; i < A.length; ++i) {
            C[K][K - A[i] + 1] = 1;
        }
        if (n <= K)
            return F[n];
        C = power(C, n - 1); 
        var result = 0;
        for (var i = 1; i <= K; ++i) {
            result = (result + C[1][i] * F[i]) % MOD;
        }
        return result;
    }
        var n = 9;
        var A = [ 0, 2, 4, 5 ];
        document.write("Number of ways = " + ways(A, n) + "\n");
</script>

Complexity Analysis:

Time Complexity: O( m2K + K3Logn ) where m is the size of Array A K is the largest element in A n denotes the stair number (nth stair) Space Complexity: O(K2)

Note:

This approach is ideal when n is too large for iteration

For Example: Consider this approach when (1 ≤ n ≤ 109) and (1 ≤ m,k ≤ 102)