Climbing Stairs LeetCode Problem
Task:- Find the number of ways you can climb the staircase of N stairs if you can take either 1 step or 2 steps at-a-time.
For eg:- If N = 3, there are 3 ways to climb the stairs:-
- Take steps — 1, 1, 1
- Take steps — 1, 2
- Take steps — 2, 1
So the answer should be 3.
Similarly, if N = 4 , no of ways = 5.
Brute Force Approach:- Consider you are at ‘i’th stair, you can go to the ‘i+1’ stair or the ‘i+2’ stair. For every stair, we can calculate the answer for both possibilities and the final answer would be the sum of both cases.
We can do the same by looking at the problem from a different perspective, Number of ways to climb the stairs will be equal to the number of climbing down the stairs if we can step down 1 or 2 steps at-a-time. Now we can recursively call a function to calculate the of ways for ‘i’th stair.
The base condition for our recursive function would be:-
- If we are at the 1st stair, there is only 1 way.
- And if we are at 2nd stair, there are 2 ways ( {1, 1} , { 2 } ).
We can put this condition simply as if i <= 2 then return i.
Brute Force Code:-
The time complexity of this approach would be O(2^N) as for every stair, we are making 2 decisions and calculating the answer for each sub-problem again & again.
Efficient Approach:- The problem with the above solution is that we are calculating answers to our sub-problems again & again when we can simply store them and re-use them whenever necessary.
So for a given N, answer = answer( N — 1 ) + answer( N — 2 ).
We can calculate problems of all the stairs from 0 to ( N — 1 ) to do so.
We can create an array & the answer to the sub-problem with stairs ‘i’ can be stored at ‘i’th index of the array.
The Answer array would be [ 0, 1, 1, 2, 3, 5, ….. ]
As we can observe the array follows the pattern of Fibonacci numbers.
Note:- The answer for ‘N’th stair can be found at the ‘N+1’st index in the answer array.
The time complexity of this approach is O(N) as we are only calculating the answer for a stair once and using it in the next steps.
Efficient code:-
