# Climbing Stairs Interview Question

This is climbing Stairs Interview question. 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 = 2Output:2Explanation:There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

**Example 2:**

Input:n = 3Output:3Explanation: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

### Approach:

Lets first start with small input. If No. of steps = 2, then we can reach step 2 in two ways. 1 step from previous step or directly taking 2 steps.

i = 2 combinations are

“1 1”

“2”

We know the to reach the ith point we can take 1 step from i-1 point or 2 steps form i-2 point. So,

**No.of ways to reach i = No.of.ways to reach i-1 + No.of.ways to reach i -2**

Example: i = 3

We can make 1 step from Combinations of i-1 ,

” 1 1″ **| ** ” 1 ”

” 2 ” **| ** ” 1″

We can make 2 step from Combinations of i-2

” 1 ” **| ** ” 2 ”

So Total Combinations = 2 + 1 = 3

To solve this we have to store the no.of ways to reach/climb each step. We can use bottom up approach. *Check out another problem solved using bottom up approach.* Bottom up approach( also known as Dynamic Programming ) means we first solve all the sub-problems and combine all the result of sub problem to find answer for original problem.

We store the subproblem result in dp array. dp[i] will contain the no.of.ways to reach ith position.

### Program:

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

### Analysis:

Time Complexity – O(n) since we traverse the input array once.

Space Complexity – O(n) since we store the subproblem results in dp array

### Another Approach:

Can we optimize it further? Yes. At each position we need only previous two results. We might not need dp array. I will leave the implementation to you. Hint: Fibonacci