Climbing Stairs

The Idea

You may step up one stair or two. To be standing on step n you must have arrived from step n-1 or from step n-2, so the ways to reach n are those two counts added together. That is Fibonacci wearing a different hat, and because nothing older is ever read, two rolling variables replace the entire table.

Real-World Example

Planking a one-metre-wide hallway with boards one and two metres long. The number of layouts for a ten-metre hall is the layouts for nine metres plus the layouts for eight, because the last board laid is either a short one or a long one.

The Code

def climb(n):
    a, b = 1, 1                  # ways to reach step 0 and step 1
    for _ in range(2, n + 1):
        a, b = b, a + b          # slide the window forward one step
    return b

print(climb(5))    # 8
print(climb(10))   # 89

def climb(n):
  a, b = 1, 1
  for _ in range(2, n + 1):
      a, b = b, ___
  return b

print(climb(6))   # should print 13