PYTHON CODE

Part C - Stairs

Write a function stairs(staircase) which takes information regarding a staircase, and returns the number of different ways it is possible to climb the staircase. The function must:

take a bitlist of length 2 representing a staircase as input.

the first and last elements of the staircase are always 1, as they represent the start and finish points.

elements in staircase that are not the first and last may be 0 or 1, where 0 represents an unsafe stair, and 1 a safe stair.

it is possible to climb the staircase by jumping one step, two steps, or three steps; but it is not possible to jump the same number of steps twice in a row.

Example: calling stairs([1,1,0,1,1]) returns 3 as it is possible to jump start-first-third-final, start-first-final, or start-third-final. Calling stairs([1,0,1,0,1]) returns 0 as it is not possible to climb the staircase, given the restrictions.

You must use backtracking to solve this problem (i.e. do not use brute force).

Calling (stairs([1,1]) will return 1

Calling (stairs([1,1,1,1,1]) will return 3

Calling (stairs([1,1,1,1,1,1,1,1,1,1]) will return 21

Calling (stairs([1,1,0,1,1,0,1,1,0,1]) will return 9