## Question:

**70. Climbing Stairs**

Type: Easy

Liked by 19.8K

Disliked by 656.

Companies that asked this question

Companies: No of times asked

Amazon 3

Yahoo 2

Adobe 11

Google 5

Apple 5

Bloomberg 3

Microsoft 3

Uber 2

Nagarro 2

Expedia 12

Oracle 4

Goldman Sachs 3

Facebook 2

Intel 2

Visa 2

Optum 2

Swiggy 2

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**Example 1:**

Input: n =`2`

Output: `2`

Explanation:

`There are two ways to climb to the top.

- 1 step + 1 step
- 2 steps`

**Example 2:**

Input: n = `3`

Output: `3`

Explanation:

`There are three ways to climb to the top.

- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step`

Constraints:

`1 <= n <= 45`

# Intuition:

The problem is about finding the number of ways to climb a staircase when you can take either 1 step or 2 steps at a time. To solve it, you can use dynamic programming.

# Approach:

Create an array to store the number of ways to reach each step.

Initialize the first two elements of the array (representing the first and second steps).

Use a loop to calculate the number of ways to reach each subsequent step.

Return the number of ways to reach the final step.

# Complexity:

**Time Complexity**: O(n)

**Space Complexity**: O(n)

# Code

```
class Solution {
public int climbStairs(int n) {
int[] arr = new int[n+1];
if(n == 1){
return 1;
}
else{
arr[1] = 1;
arr[2] = 2;
for(int i = 3 ; i <=n ; i++){
arr[i] = arr[i-1] + arr[i-2];
}
}
return arr[n];
}
}
```

Happy coding,

shiva

## Top comments (0)