Triple Step (Puzzle 8.1. from "Cracking the Coding Interview")

count_steps.py

def count_steps(n):
    """Determine how many ways there are to walk n steps, if you can jump over 1, 2 or 3 steps at the time
    
    f(-1) = 0
    f(0) = 1 # just stand?
    f(1) = 1
    f(2) = 2 
    f(3) = 4
    f(4) = f(n-1)+f(n-2)+f(n-3)
    
    Algo#1: bruteforce recursion. f(n)=f(n-1)+f(n-2)+f(n-3). Complexity: O(3^n)
    
    Algo#2: bottom-up approach. We build a sequence:
    f(0)
    f(1)
    f(2)
    ...
    f(n) = f(n-1)+f(n-2)+f(n-3)
    
    Complexity: space: O(1), time: O(n)
    
    Parameters
    ----------
    n: int
        number of steps
    
    Returns
    -------
    n_steps: int
        number of ways to traverse n steps
    
    """
    
    if n<0:
        return 0
    
    if n==0 or n==1:
        return 1
    
    buf = [0, 1, 1]
    
    # n>2
    for i in range(2, n+1):
        curr = buf[-3]+buf[-2]+buf[-1]
        buf[-3] = buf[-2]
        buf[-2] = buf[-1]
        buf[-1] = curr
    
    return curr

# DEMO
for i in range(-1, 20):
    print("steps: %d, n_variants: %d" % (i, count_steps(i)))