# 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