Search

# Solution of Staircase Problem

Updated: May 17, 2020

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.

See All