Data Structures & Algorithms – Dynamic Programming – Climbing Stairs

Problem:

Given a step number in a stair case , find the number of ways you can reach that step in the staircase if you can make 1 or 2 steps at a time

Input:

4

Output:

5 ways

Since you can take any of the below sequence of steps:

[1,1,1,1] , [1,2,1],[1,1,2] ,[2,1,1], [2,2]

Try out the solution here:

https://leetcode.com/problems/climbing-stairs

Solution:

There is a recursive way to solve this problem and also the way of dynamic programming.

Both make use of the following hint:

Hint:

The number of different ways to climb a stairs at any step (1 or 2 steps at a time ) = The number of different ways to climb until the previous step + The number of different ways to climb until the previous to previous step

Ways to climb nth step = ways to climb (n-1)th step +ways to climb (n-2)th step

Recursive Solution:

The recursive solution to the problem is to cover the base cases first and then call the recursive method for the previous step and the previous to previous step.

Here is the code:

class Solution {
    public int climbStairs(int n) {
     
        if(n == 0|| n ==1 || n==2){
            
            return n;
        }
        
   
        
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

If it is a single step or two steps , there are 1 and 2 ways to climb the stairs respectively as you can imagine .

Single step – 1 step

Two steps – 1 step + 1 step , 2 steps

For the third step , you add the number of ways to climb 2 steps (2) and the number of ways to climb 1 step (1) which is equal to 3.

And it goes on for each successive steps.

This solution is expensive since the time complexity is 2^n since each recursive call makes two more recursive calls and they each in turn make two more recursive calls and so on.

A better solution exists using Dynamic Programming.

Dynamic Programming:

In Dynamic Programming , you compute the solution for smaller sub problems and use those solutions to compute the bigger problem.

In the recursive case , the same recursive call is made multiple times at different positions of the recursive tree. This can be avoided in Dynamic Programming.

Since the solution to the current problem as earlier mentioned in the hint involves adding up the solution of previous two sub problems , you can rewrite the algorithm this way

ALGORITHM:

STEP1: Initialize three variables , one to store the previous solution (n-1) , another to store the previous to previous (n-2) solution and another to store the result

STEP2: Declare the base solutions , If number of steps is 0 , the result is 0 , if it is 1 , the result is 1 , if it is 2 , the result is 2.

STEP3: For the rest of the steps , find the solution by adding the result of the previous two solutions, keep changing the value of the variable pointing to the previous solution and previous to previous solution accordingly

Code:

    class Solution {
        public int climbStairs(int n) {
            int prevStep = 2;
            int prevToPrevStep = 1;
            int totalWays = 0;
            if(n==0||n==1||n==2){
                
                return n;
            }
           for(int i=3;i<=n;i++){
               
               totalWays = prevStep + prevToPrevStep;
               
               prevToPrevStep = prevStep;
               
               prevStep = totalWays;
           }
            
            return totalWays;
        }
    }

The time complexity of the above algorithm is O(n) and space complexity is O(1).

That’s it!