Climbing Stairs

You can take one step or two steps at a time, and you need to reach the top of a staircase of n steps. The number of ways to reach step k is the number of ways to reach step k minus one plus the number of ways to reach step k minus two, because the last move was either one step or two steps.

That makes the answer the n plus one Fibonacci number, and the base cases are one way to reach step zero and one way to reach step one.

The mechanism is that the two cases partition all the possible routes, so the counts add without double counting. This is a textbook demonstration of the dynamic programming shape: a small state, a recurrence over neighbouring states, and a base case.

The trade-off to name is that the same answer can be produced by very different amounts of work. The naive recursive solution explores exponentially many routes, the bottom up table takes linear time and linear space, and the rolling two variable version takes linear time and constant space. The other point is that a greedy approach does not work here, because choosing the larger step is not always safe: the greedy choice can leave you unable to finish, which is exactly the situation dynamic programming is designed for.

Only the previous two counts are needed, so keep them in two variables and update them together.

def climb_stairs(n):
    previous, current = 1, 1
    for _ in range(2, n + 1):
        previous, current = current, previous + current
    return current


print(climb_stairs(5))
print(climb_stairs(10))

The outputs are 8 and 89. There are eight ways to climb five steps and eighty nine ways to climb ten.

The mechanism is that the recurrence at step k only refers to steps k minus one and k minus two, so a window of two values carries everything the next step needs. The simultaneous assignment computes both new values from the old pair before either is overwritten.

The trade-off to name is the space, which drops from linear in the table version to constant here, at the cost of not being able to answer questions about intermediate steps. If you needed to know how many ways reach every step, the table version would be the right one. The other thing to say is that this problem is really Fibonacci in disguise, so a candidate who spots that can also mention fast doubling for logarithmic time when n is very large.

Fill an array where each entry holds the number of ways to reach that step, building from the base cases upwards.

def climb_stairs(n):
    if n <= 1:
        return 1
    table = [0] * (n + 1)
    table[0] = 1
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(climb_stairs(5))
print(climb_stairs(1))

The outputs are 8 and 1. There is one way to climb a single step and eight ways to climb five.

The mechanism is that the table is filled in increasing order, so by the time you compute the value for step i, both values it depends on are already in the array. The base case of one way to reach step zero is what makes the table start correctly, since there is exactly one empty route to the ground.

The trade-off to name is the space, which is linear in the number of steps because every intermediate count is kept. The rolling version in the previous answer gets the same answer in constant space, and it is worth explaining why: the table only exists because you might want to look at the intermediate values later, and if you do not, the last two are enough. The other point is that the numbers grow fast, since they are Fibonacci numbers, so a language with fixed width integers would overflow for a large staircase.