- Problem Statement
- Brute Force (Recursive) Approach
- C++ Implementation of Recursive Approach
- Java Implementation of Recursive Approach
- Python Implementation of Recursive Approach
- Bottom-up Approach
- C++ Implementation of DP Approach
- Java Implementation of DP Approach
- Python Implementation of DP Approach
- Fibonacci Number Approach
- Practice Question
- FAQs

## Problem Statement

Given a staircase of **N** steps you can either climb 1 or 2 steps at a given time. The task is to return the count of distinct ways to climb to the top.**Note: **The order of the steps taken matters.

**Examples:**

**Input: **N = 3**Output: **3**Explanation:**

### Confused about your next job?

There are three distinct ways of climbing a staircase of 3 steps :

[1, 1, 1], [2, 1] and [1, 2].**Input: ** N = 2**Output:** 2**Explanation:**

There are two distinct ways of climbing a staircase of 3 steps :

[1, 1] and [2].## Brute Force (Recursive) Approach

The approach is to consider all possible combination steps i.e. 1 and 2, at every step. To reach the **Nth** stair, one can jump from either (**N – 1)th **or from** (N – 2)th **stair. Hence, for each step, total ways would be the summation of (**N – 1)th stair + (N – 2)**th stair.

The recursive function would be:

**ClimbStairs(N) = ClimbStairs(N – 1) + ClimbStairs(N – 2)**.

If we observe carefully, the expression is nothing but the **Fibonacci Sequence**.

SampleRecursive Tree for **N = 5**:

**Algorithm:**

- If
**N < 2,**return**1**. This is the termination condition for the function. - Else, find the summation of
**ClimbStairs(N – 1) + ClimbStairs(N – 2)**.

### C++ Implementation of Recursive Approach

int climbStairs(int N) { if ( N < 2 ) return 1; else return climbStairs(N-1) + climbStairs(N-2); }

### Java Implementation of Recursive Approach

static int climbStairs(int N){ if ( N < 2 ) return 1; else return climbStairs(N-1) + climbStairs(N-2); }

### Python Implementation of Recursive Approach

def climbStairs(N): if N < 2 : return 1 else: return climbStairs(N-1) + climbStairs(N-2)

## Bottom-up Approach

In the above approach, observe the recursion tree. It can be clearly seen that some of the subproblems are repeating. Hence, it is unnecessary to calculate those again and again. Therefore, we can store the result of those subproblems and retrieve the solution of those in O(1) time.

Since the problem contains an optimal substructure and has overlapping subproblems, it can be solved using **dynamic programming**.

One can reach the **ith** step in one of the two ways :

- Take one step from
**(i – 1)th step.** - Take two steps from
**(i – 2)th step.**

**Algorithm**

- Initialise a
**dp[]**array of size**N + 1**. - Assign
**dp[0]**and**dp[1]**to 1. - Iterate a loop from
**2**till**N**and for each iteration:**dp[i] = dp[i – 1] + dp[i – 2]**

- Return the value of
**dp[N]**.

### C++ Implementation of DP Approach

int climbStairs(int N) { int dp[N+1]; dp[0] = 1 dp[1] = 1 for (i = 2; i <= N; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[N]; }

### Java Implementation of DP Approach

static int climbStairs(int N) { int dp[] = new int[N+1]; dp[0] = 1 dp[1] = 1 for (i = 2; i <= N; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[N]; }

### Python Implementation of DP Approach

def climbStairs(N): dp = [0]*(N + 1) dp[0] = 1 dp[1] = 1 for i in range(2, N + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[N]

## Fibonacci Number Approach

In the above approach, the **dp** array is just storing the value of the previous two steps from the current **ith** position i.e. **(i – 1)th **and **(i – 2)th **position.

The space complexity can be further optimized, since we just have to find an **Nth** number of the Fibonacci series having 1 and 2 as their first and second term respectively, i.e. **Fib(1) = 1 and Fib(2) = 2**.

**Algorithm**

- Initialise two variables
**first = 1**and**second = 2**. - Iterate a loop from
**i = 3**till**i = N**and for each step:- Initialise a variable
**third = first + second** **first = second****second = third**

- Initialise a variable
- Return
**second**after the iteration ends.

### C++ Implementation

int climbStairs(int N) { if (N == 1) { return 1; } int first = 1; int second = 2; for (int i = 3; i <= N; i++) { int third = first + second; first = second; second = third; } return second; }

#### Java Implementati**on**

public int climbStairs(int N) { if (N == 1) { return 1; } int first = 1; int second = 2; for (int i = 3; i <= N; i++) { int third = first + second; first = second; second = third; } return second; }

#### Python Implementation

def climbStairs(N): if N == 1: return 1 first = 1; second = 2; for i in range(3, N + 1): third = first + second; first = second; second = third; return second;

## Practice Question

## FAQs

### Q.1: What is the most efficient approach to solving the Climbing stairs problem?

**Ans**: The approach to finding the Nth Fibonacci number is the most efficient since its time complexity is O(N) and space complexity is O(1).

### Q.2: How to solve this problem if it’s given that one can climb up to K steps at a time?

**Ans:** If one can climb **K** steps at a time, try to find all possible combinations from each step from **1** to **K. **

The recursive function would be :**climbStairs(N, K) = climbStairs(N – 1, K) + climbStairs(N – 2, K) + … + climbStairs(N – K , K).**