Number of ways to climb a staircase with n steps, given a list of possible jumps.

num_ways.py

"""
Given a number of steps _n_, and a list of possible _jumps_,
what's the number of different ways to climb the staircase ?
"""

def num_ways(n, jumps):
    if n <= 1:
        return 1
    return sum([num_ways(n-j, jumps) for j in jumps if n-j >= 0])


def num_ways_memo(n, jumps, cache={}):
    if n <= 1:
        return 1

    total = 0
    for j in jumps:
        if n-j < 0:
            continue

        if (n-j, jumps) not in cache:
            cache[(n-j,jumps)] = num_ways_memo(n-j, jumps)
        total += cache[(n-j,jumps)]

    return total


def num_ways_bottom_up(n, jumps):

    dp = [0 for _ in range(n + 1)]
    dp[0] = 1

    for i in range(1, n + 1):
        for j in jumps:
            if i - j >= 0:
                dp[i] += dp[i-j]

    return dp[-1]