Climbing the staircase

Tags: , ,

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 2 steps at a time, in how many possible ways can we climb to the top? For example, let N = 3 i.e. there are 3 steps to climb. In this case, we can reach the top by:
– 1 step, 1 step, 1 step
– 1 step, 2 steps
– 2 steps, 1 step
So there are 3 possible ways to reach the top if we can take {1, 2} steps at a time.

How can we think of a solution? At the position that we are currently standing (be it start of the staircase or in the middle somewhere on the staircase) we have two choices, we can either climb 1 step or we can climb 2 steps. This also means that we reached our current position on the staircase by climbing either 1 step or 2 steps, i.e. if we are at step say x we reached here by climbing from either (x-1)th step or (x-2)th step. To actually find in how many ways we can reach x, we need to know in how many ways we reached x-1 and x-2 in the first place and then add them to find the number of ways to reach x. To make this easier to understand let’s look at some examples.

Consider we are at step 0 (ground) and the staircase has just 1 step, so the number of ways to reach the top is:
1st way : [0🡪1] => take 1 step and we reach the top.
Climbing staircase

Consider the staircase has 2 steps, so the number of ways to reach the top is:
1st way: [0🡪1🡪2] => take 1 step at a time and climb one by one step to reach the top
2nd way: [0🡪2] => take 2 steps and reach the top
Climbing staircase

Consider the staircase has 3 steps, so the number of ways to reach the top is:
now consider we are actually at the top at step 3, according to our thoughts above we can reach step 3 (x) either by from step 2 (x-1) or from step 1 (x-2). Let’s consider the case for step 1 (x-2) first: We already know number of ways to reach step 1 and that is 1 =>
1) [0🡪1]: using this we reach step 3 => [0🡪1🡪3].

Similarly, we already know the number of ways to reach step 2 and that are 2 =>
1) [0🡪1🡪2]: using this we get another way to reach step 3 => [0🡪1🡪2🡪3] 2) [0🡪2]: using this we get another way to reach step 3 => [0🡪2🡪3].

So finally we have our three ways to reach step 3:
[0🡪1🡪3], [0🡪1🡪2🡪3], and [0🡪2🡪3].

Notice that we just added 3 to already known paths for step 1 and step 2.

Consider the staircase has 4 steps, so the number of ways to reach the top is:
number of ways to reach step 2 (x-2) + number of ways to reach step 3 (x-1) = 5
From step 2: [0🡪1🡪2🡪4], [0🡪2🡪4] From step 3: [0🡪1🡪3🡪4], [0🡪1🡪2🡪3🡪4] and [0🡪2🡪3🡪4].

So from the examples we understand that: total_ways(n) = total_ways(n-1) + total_ways(n-2).

Note that this means this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).
This formula is similar to the one we used to find Nth Fibonacci number. Actually total_ways(n) = findNthFib(n+1).

Notice it is (N+1)th Fibonacci number and not Nth, that’s because of the bases cases from where we start our calculations. Consider a case that the staircase has 0 steps to climb and we start from the ground (i.e. step 0), so in this case we argue that there’s only 1 way to reach the top i.e. [0].
With this argument:
total_ways(0) = 1, total_ways(1) = 1…
findNthFib(0) = 0, findNthFib(1) = 1, findNthFib(2) = 1…
and hence the formula total_ways(n) = findNthFib(n+1).

There’s another variation of this problem where the number of steps that can be taken at a time is not limited to just {1, 2}.

Total possible ways to climb a staircase (variation 2)

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 2 or 3 steps at a time, in how many possible ways can we climb to the top?
For example, let n = 3 i.e. there are 3 steps to climb. In this case, we can reach the top by:
– 1 step, 1 step, 1 step
– 1 step, 2 steps
– 2 steps, 1 step
– 3 steps
So there are 4 possible ways to reach the top of a staircase of 3 steps if we can take {1, 2, 3} steps at a time

Similar to the approach taken above, we can reach our current position on staircase by climbing either 1 step or 2 steps or 3 steps, i.e. if we are at step say x we reached here by climbing from either x-1th step or x-2th step or x-3th step. So to actually find in how many ways we can reach x, we need to know in how many ways we reached x-1, x-2 and x-3 in the first place and then adding them will give number of ways to reach x.

total_ways(n) = total_ways(n-1) + total_ways(n-2) + total_ways(n-3)
This formula maps to a recursive solution:

long long int findTotalWays (int n)
{
    if(n == 0 || n == 1) return 1;
   if(n == 2) return 2;
    return findTotalWays(n-1) + findTotalWays(n-2) + findTotalWays(n-3);
}
 
int main(void) 
{
    int N = 5;
    long long int total_ways = findTotalWays(N);
    printf("%lld", total_ways);
    return 0;
}

But this solution is not feasible as it has exponential time complexity. To find the reason behind this let’s look at the function call tree:

As we can see here that the subproblems such as total_ways(3) and total_ways(2) are calculated repeatedly. This means that the subproblems are overlapping.
As the two properties required for using dynamic programming : optimal substructure and overlapping subproblems hold true, we can use DP for this problem.

int main(void) 
{
    int N = 5;
    vector<long long int> DPVec(N+1, 0);
    DPVec[0] = 1; DPVec[1] = 1; DPVec[2] = 2;
    for (int i=3; i<=N; ++i)
    {
          DPVec[i] = DPVec[i-1] + DPVec[i-2] + DPVec[i-3];
    }
    printf("%lld", DPVec[N]);
    return 0;
}

The time and space complexity of the implementation is O(n).

Total possible ways to climb a staircase (variation 3)

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 3 or 5 steps at a time, in how many possible ways can we climb to the top? To generalize we can be given any set of the allowed number of steps that can be taken at a time and we have to find the number of possible ways to climb to the top?

Keeping in mind the above described approach, the formula again here is: total_ways(n) = total_ways(n-1) + total_ways(n-3) + total_ways(n-5) As negative step does not make any sense, we will recur for non-negative steps only.

long long int findTotalWays (int n, vector<int> &Step_Set)
{
    if(n == 0) return 1;
   long long int total_ways = 0;
   for(int i=0; i<Step_Set.size();++i)
   {
        if ((n – Step_Set[i]) >= 0)
             total_ways += findTotalWays(n- Step_Set[i], Step_Set);
   }
    return total_ways;
}
 
int main(void) 
{
    int N = 5;
    vector<int> Step_Set{1, 3, 5};
    long long int total_ways = findTotalWays(N, Step_Set);
    printf("%lld", total_ways);
    return 0;
}

Dynamic programming solution for the problem

int main(void) 
{
    int N = 5;
    vector<int> Step_Set{1, 3, 5};
    vector<long long int> DPVec(N+1, 0);
    DPVec[0] = 1;
    for (int i=1; i<=N; ++i)
    {
         for (int j=0; j<Step_Set.size(); ++j)
        {
               if ((i – Step_Set[j]) >= 0)
              {
                   DPVec[i] += DPVec[i- Step_Set[j]];
              }
        }
    }
    printf("%lld", DPVec[N]);
    return 0;
}

The time is O(m*n) and space complexity: O(m + n) where m is size of the set of allowed steps and n is the number of steps in the staircase. These implementations work in general for any set of allowed steps.

This article is contributed by Bhushan Aggrawal.