# 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