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 = 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
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:
[code lang=”java”]
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];
}
}
[/code]
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