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. 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