Triple Step

A child is running up a staircase with n steps and can hop either 1 setp, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Solution

A basic recursive solution will explore all of the possible decision trees, and count all of the paths which add up to n steps. At each branch of the decision tree, we have three options : taking 1, 2 or 3 steps. The function will make 3 recursive calls to itself in order to map out the entire decision tree.

def traverse(n):
  if(n < 0):
    return 0
  elif(n == 0):
    return 1

  count = 0
  count += traverse(n-1)
  count += traverse(n-2)
  count += traverse(n-3)

  return count

You’ll notice that the number of ways increases exponentially with the number of steps. For 10 steps, there are 274 ways of climbing them. For 20 steps, there are 121,415 ways of climbing them. This solution is not scalable, and in order to craft a better solution we need to take advantage of the shared subspaces between problems. Let’s memoize the solutions so we don’t have to compute them more than once.

def traverse(n, memo):
  if(n < 0):
    return 0
  elif(n == 0):
    return 1
  elif(memo[n]):
    return memo[n]

  memo[n] = 0
  memo[n] += traverse(n-1, memo)
  memo[n] += traverse(n-2, memo)
  memo[n] += traverse(n-3, memo)

  return memo[n]