Hackbright Code Challenges

Staircase Steps

Staircase Steps

Challenge

Harder

Concepts

Recursion, Dynamic Programming

Download

staircase-steps.zip

Solution

Staircase Steps: Solution


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:

steps.py
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.