Davis has staircases in his house and he likes to climb each staircase 1, 2 or 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase.

recursive_staircase.py

def recursive_staircase(height):
    steps = [1,2,3]
    ways = 0
    
    for step in steps:
        if step == height:
            ways += 1
            break
        elif step < height:
            ways += recursive_staircase(height - step)
    
    return ways

cache = dict()
def recursive_staircase_memo(height):
    steps = [1,2,3]
    ways = 0
    
    if height in cache:
        return cache[height]
    
    for step in steps:
        if step == height:
            ways += 1
            break
        elif step < height:
            ways += recursive_staircase(height - step)
    
    cache[height] = ways
    return ways


def recursive_staircase_cycle(height):
    paths = [1,1,2]
    i=3

    while i <= height:
        paths.append(paths[i-1] + paths[i-2] + paths[i-3])
        i += 1

    return paths[height]

def recursive_staircase_dp(height):
    if height <= 1 :
        return 1

    paths = [1,1,2]
    i=3
    
    while i <= height:
        tmp = paths[0] + paths[1] + paths[2]
        paths = [paths[1], paths[2], tmp]
        i += 1

    return paths[2]

if __name__ == '__main__':
    assert recursive_staircase(4) == 7
    assert recursive_staircase_memo(4) == 7
    assert recursive_staircase_cycle(4) == 7
    assert recursive_staircase_dp(1) == 1
    assert recursive_staircase_dp(4) == 7