Recursion, Dynamic Programming
First, imagine the problem of a staircase with 1 step. You can clearly climb it 1 way.
Now, imagine the problem of a staircase with 2 steps. You can climb is 2 ways:
climbing 2 steps at once (“2”)
climbing 1 step, then 1 more step (“11”)
For 3 steps:
“111”
“12”
“21
“3”
At any point, you can climb 1, 2, or 3 steps – so we can develop a recursive algorithm that tries taking 1 step from where we are, 2 steps from where are, and 3 steps from where we are. If that path is successful, we’ll count it.
For a staircase with 1 step:
For a staircase with 2 steps:
For a staircase with 3 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.
"""
# START SOLUTION
# Base case:
#
# It might seem strange to think there's a way to take zero
# staircase-steps --- but this is really a saying "this path of recursion"
# is successful, since it ended up using exactly the right number
# of staircase-steps
if n == 0:
return 1
# If we overshoot, this was not a successful path
if n < 1:
return 0
# The way to take n number of staircase-steps is the way to take
# n - 1 staircase-steps, n - 2 staircase-steps, and n - 3 staircase-steps,
# all added up (since we can always take 1, 2, or 3 more staircase-steps
# afterwards)
return steps(n - 1) + steps(n - 2) + steps(n - 3)
There’s a lot of repetition in what it has to calculate. A more advanced solution can use a concept called “memoization” to remember the solution to already-solved problems.
This moves the problem from being just a recursive solution to one using “dynamic programming” — a good intermediate concept to learn about!
A dynamic programming version is similar, and lets use computer much, much larger staircases:
def steps_cache(n):
"""How many different ways can you climb a staircase of `num` steps?
You can climb 1, 2, or 3 steps at a time.
In this version, we're caching previous work, so we can do much
longer calculations.
For 100 steps: 180,396,380,815,100,901,214,157,639 different ways!
>>> steps_cache(100)
180396380815100901214157639
"""
# Cache previous work, so we don't keep having to re-calculate
# answers we've already derived. This changes the runtime from
# O(3**n) to the much, much better O(3n)
#
# ``cache`` will hold the results of taking each number of staircase-steps
cache = [None] * (n + 1)
def _steps(n):
"""How many ways are there to take `n` steps?"""
# Base case:
#
# It might seem strange to think there's a way to take zero
# staircase-steps --- but this is really a saying "this path of recursion"
# is successful, since it ended up using exactly the right number
# of staircase-steps
if n == 0:
return 1
# If we overshoot, this was not a successful path
if n < 1:
return 0
# If we haven't already cached this work, do so
if cache[n] is None:
cache[n] = _steps(n - 1) + _steps(n - 2) + _steps(n - 3)
return cache[n]
return _steps(n)