1. Home
  2. Climbing Stairs Problem using Matrix Exponentiation

Climbing Stairs Problem using Matrix Exponentiation

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:

01
11

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):

1
2

As an example, For n= 4: 

F(4) = C3F(1)

C3 = 

12
23

Hence, C3F(1) = 

5
8
C++ 
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;

#define LOOP(i, n) for (int i = 1; i < n; i++)

// Computes A*B
// where A,B are square matrices
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;
}

// Computes A^n
matrix power(matrix A, long long n)
{
    if (n == 1)
        return A;
    if (n % 2 != 0) {
        // n is odd
        // A^n = A * [ A^(n-1) ]
        A = mul(A, power(A, n - 1));
    }
    else {
        // n is even
        // A^n = [ A^(n/2) ] * [ A^(n/2) ]
        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;
    // create K*K matrix
    matrix C(K + 1, vector<long long>(K + 1, 0));
    /*
      A matrix with (i+1)th element as 1 and last row
      contains constants
      [
          [0 1 0 0 ... 0]
          [0 0 1 0 ... 0]
          [0 0 0 1 ... 0]
          [. . . . ... .]
          [. . . . ... .]
          [c(k) c(k-1) c(k-2) ... c1]
      ]
    */
    for (int i = 1; i < K; ++i) {
        C[i][i + 1] = 1;
    }
    // Last row is the constants c(k) c(k-1) ... c1
    // f(n) = 1*f(n-1) + 1*f(n-2)
    C[K][1] = 1;
    C[K][2] = 1;

    if (n <= 2)
        return F[n];

    // f(n) = C^(n-1)*F
    C = power(C, n - 1);

    long long result = 0;

    // result will be the first row of C^(n-1)*F
    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;
}

// This code is contributed by darshang631
Java 
import java.util.*;

class GFG {

    // Computes A*B
    // where A,B are square matrices
    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;
    }

    // Computes A^n
    static long[][] power(long[][] A, long n)
    {
        if (n == 1)
            return A;
        if (n % 2 != 0) {

            // n is odd
            // A^n = A * [ A^(n-1) ]
            A = mul(A, power(A, n - 1), 1000000007);
        }
        else {
            // n is even
            // A^n = [ A^(n/2) ] * [ A^(n/2) ]
            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;

        // create K*K matrix
        long[][] C = new long[K + 1][K + 1];
        /*
         * A matrix with (i+1)th element as 1 and last row
         * contains constants [ [0 1 0 0
         * ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . .
         * ... .] [. . . . ... .] [c(k) c(k-1) c(k-2) ...
         * c1] ]
         */
        for (int i = 1; i < K; ++i) {
            C[i][i + 1] = 1;
        }
        // Last row is the constants c(k) c(k-1) ... c1
        // f(n) = 1*f(n-1) + 1*f(n-2)
        C[K][1] = 1;
        C[K][2] = 1;

        if (n <= 2)
            return F[n];

        // f(n) = C^(n-1)*F
        C = power(C, n - 1);

        long result = 0;

        // result will be the first row of C^(n-1)*F
        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");
    }
}

// This code is contributed by umadevi9616
Python 
# Computes A*B
# where A,B are square matrices


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

# Computes A^n


def power(A,  n):
    if (n == 1):
        return A
    if (n % 2 != 0):

        # n is odd
        # A^n = A * [ A^(n-1) ]
        A = mul(A, power(A, n - 1), 1000000007)
    else:
        # n is even
        # A^n = [ A^(n/2) ] * [ A^(n/2) ]
        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

    # create K*K matrix
    C = [[0 for i in range(K+1)] for j in range(K+1)]
    '''
     * A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
     * ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
     * c(k-1) c(k-2) ... c1] ]
     '''
    for i in range(1, K):
        C[i][i + 1] = 1

    # Last row is the constants c(k) c(k-1) ... c1
    # f(n) = 1*f(n-1) + 1*f(n-2)
    C[K][1] = 1
    C[K][2] = 1

    if (n <= 2):
        return F[n]

    # f(n) = C^(n-1)*F
    C = power(C, n - 1)
    result = 0

    # result will be the first row of C^(n-1)*F
    for i in range(1, K+1):
        result = (result + C[1][i] * F[i]) % MOD

    return result


# Driver code
if __name__ == '__main__':
    n = 4
    print("Number of ways = ", ways(n), "")

# This code is contributed by gauravrajput1
C# 
using System;

public class GFG {

    // Computes A*B
    // where A,B are square matrices
    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;
    }

    // Computes A^n
    static long[, ] power(long[, ] A, long n)
    {
        if (n == 1)
            return A;
        if (n % 2 != 0) {

            // n is odd
            // A^n = A * [ A^(n-1) ]
            A = mul(A, power(A, n - 1), 1000000007);
        }
        else {
            // n is even
            // A^n = [ A^(n/2) ] * [ A^(n/2) ]
            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;

        // create K*K matrix
        long[, ] C = new long[K + 1, K + 1];
        /*
         * A matrix with (i+1)th element as 1 and last row
         * contains constants [ [0 1 0 0
         * ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . .
         * ... .] [. . . . ... .] [c(k) c(k-1) c(k-2) ...
         * c1] ]
         */
        for (int i = 1; i < K; ++i) {
            C[i, i + 1] = 1;
        }
        // Last row is the constants c(k) c(k-1) ... c1
        // f(n) = 1*f(n-1) + 1*f(n-2)
        C[K, 1] = 1;
        C[K, 2] = 1;

        if (n <= 2)
            return F[n];

        // f(n) = C^(n-1)*F
        C = power(C, n - 1);

        long result = 0;

        // result will be the first row of C^(n-1)*F
        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");
    }
}

// This code is contributed by umadevi9616
Javascript 
    // Computes A*B
    // where A,B are square matrices
     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;
    }

    // Computes A^n
     function power( A , n) {
        if (n == 1)
            return A;
        if (n % 2 != 0) {

            // n is odd
            // A^n = A * [ A^(n-1) ]
            A = mul(A, power(A, n - 1), 1000000007);
        } else {
            // n is even
            // A^n = [ A^(n/2) ] * [ A^(n/2) ]
            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;

        // create K*K matrix
    var  C = Array(K+1).fill().map(()=>Array(K+1).fill(0));
        /*
         * A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
         * ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
         * c(k-1) c(k-2) ... c1] ]
         */
        for (var i = 1; i < K; ++i) {
            C[i][i + 1] = 1;
        }
        // Last row is the constants c(k) c(k-1) ... c1
        // f(n) = 1*f(n-1) + 1*f(n-2)
        C[K][1] = 1;
        C[K][2] = 1;

        if (n <= 2)
            return F[n];

        // f(n) = C^(n-1)*F
        C = power(C, n - 1);

        var result = 0;

        // result will be the first row of C^(n-1)*F
        for (var i = 1; i <= K; ++i) {
            result = (result + C[1][i] * F[i]) % MOD;
        }
        return result;
    }

        var n = 4;
        console.log("Number of ways = " + ways(n) + "\n");

// This code is contributed by umadevi9616

Output
Number of ways = 5

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



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)

Similar Reads

Climbing Stairs using Recursion:

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 Recurrence relation for such an approach comes out to be :...

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....

Climbing Stairs using Dynamic Programming (Tabulation):

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

Climbing Stairs 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....

Climbing Stairs Problem using Mathematics:

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

Climbing Stairs Problem using Matrix Exponentiation:

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...

Categories

HTML CSS3 Bootstrap Foundation Sass JavaScript TypeScript JQuery AngularJS React NodeJS Highcharts PHP Python Python3 Django Linux Docker Ruby Java C C ++ Perl Servlet JSP Lua Scala Go ASP C # SQL MySQL SQLite MongoDB Redis Android Swift ionic Kotlin XML tutorial

Contact US