# Climbing stairs

Difficulty Level Easy
Dynamic ProgrammingViews 1144

## Problem Statement

The problem “Climbing stairs” states that you are given a staircase with n stairs. At a time you can either climb one stair or two stairs. How many numbers of ways to reach the top of the staircase?

## Example

`3`
`3`

Explanation

There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step The image shows the ways to move.

## Recursive Approach

We can observe that number of ways to reach ith stair is the summation of the number of ways to reach (i-1)the stair and number of ways to reach (i-2)th stair. So our recursive equation becomes

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

### Code

#### C++ code for Climbing Stairs

```#include <bits/stdc++.h>
using namespace std;

// A recursive function used by countWays
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;
}

// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}

// Driver code
int main()
{
int s = 4, m = 2;
cout << "Nuber of ways = " << countWays(s, m);

return 0;
}```
`5`

#### Java code for Climbing Stairs

```class stairs {
// A recursive function used by countWays
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;
}

// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}

/* Driver program to test above function */
public static void main(String args[])
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
}```
`5`

### Complexity Analysis

#### Time Complexity

O(2^n), because in recursive approach for each stair we have two options: climb one stair at a time or climb two stairs at a time. As we are checking for all possible cases so for each stair we have 2 options and we have total n stairs so time complexity becomes O(2^n)

#### Space Complexity

O(n) because space is required by the compiler to use recursion. The recursion also requires stack and thus storing that makes this O(n) space because recursion will be almost n deep.

## Dynamic Programming Approach

The recursive approach includes the recomputation of the same values again and again. For this we use memoization and when we calculate it for some input we store it in the memoization table. When we need it later we don’t compute it again and directly use its value from the table. We maintain table ways[] where ways[i] stores the number of ways to reach ith stair. So ways[n-1] is our answer.

### Code

#### C++ code for Climbing Stairs

```#include <stdio.h>

// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
int res[n];
res = 1;
res = 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];
}

// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}

// Driver program to test above functions
int main()
{
int s = 4, m = 2;
printf("Number of ways = %d", countWays(s, m));
return 0;
}
```
`5`

#### Java code for Climbing Stairs

```// Java program to count number of ways
// to reach n't stair when a person
// can climb 1, 2, ..m stairs at a time

class stairs {
// A recursive function used by countWays
static int countWaysUtil(int n, int m)
{
int res[] = new int[n];
res = 1;
res = 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];
}

// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}

// Driver method
public static void main(String[] args)
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
}```
`5`

### Complexity Analysis

#### Time Complexity

O(m*n) here m is the number of ways which is 2 for this problem and n is the number of stairs.

#### Space Complexity

O(n) because we are using an array of size n where each position stores number of ways to reach till that position.

Translate »