Recursion, Dynamic Programming
Imagine, on a flight of stairs, that you can climb either 1, 2, or 3 steps at a time.
One a staircase with three steps, you could do this in 4 different ways:
take 1 step, 1 step, and 1 step (“111”)
take 1 step, and 2 steps (“12”)
take 2 steps and 1 step (“21”)
take 3 steps (“3”)
On a staircase with 4 steps, you could this 7 ways: “1111”, “121”, “211”, “112”, “22”, “13”, “31”.
Write a function that calculates the number of ways you could climb a staircase of n steps.
We’ve provided a file, steps.py, with a function steps:
def steps(n):
"""How many different ways can you climb a staircase of `n` steps?
You can climb 1, 2, or 3 steps at a time.
"""
Implement the function steps.