Solution of Staircase Problem

If you haven't give it a try please first look at the problem here

Lets try to understand the problem. if we look at the sequence it is nothing but a Fibonacci series. so we can write a program to calculate the value at the given index(no of staircases).

def staircase(n):
    if n==1:
        return 1
    if n==2:
        return 2
    if n==3:
        return 4
    return staircase(n-1)+staircase(n-2)+staircase(n-3)

Input: 4

Output: 7

Input: 5

Output: 13

Lets try with some visualization how our function is working.

see the below tree to understand the workflow of our function.

---

Another Faster Solution Using cashing the values

def staircase(n):
    num_dict = dict({})
    return staircase_faster(n, num_dict)

def staircase_faster(n, num_dict):
    if n == 1:
        output = 1
    elif n == 2:
        output = 2
    elif n == 3:
        output = 4
    else:
        if (n - 1) in num_dict:
            first_output = num_dict[n - 1]
        else:
            first_output =  staircase_faster(n - 1, num_dict)
        
        if (n - 2) in num_dict:
            second_output = num_dict[n - 2]
        else:
            second_output = staircase_faster(n - 2, num_dict)
            
        if (n - 3) in num_dict:
            third_output = num_dict[n - 3]
        else:
            third_output = staircase_faster(n - 3, num_dict)
        
        output = first_output + second_output + third_output
    
    num_dict[n] = output;
    return output

Using above program we don't have to calculate value for 3,2 again as we did it on the level 1 of the tree as shown in the figure.

Stay tuned for more.

Follow Programmers Door for more.

#programming #interview #blog