Leetcode

Posted on

# Solving "Climbing Stairs" Leet code Problem

## 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
Apple 5
Bloomberg 3
Microsoft 3
Uber 2
Nagarro 2
Expedia 12
Oracle 4
Goldman Sachs 3
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. 1 step + 1 step
2. 2 steps`

Example 2:
Input: n = `3`
Output: `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`

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