A staircase has n steps. You can scale the stairs by taking steps one or two at a time. How many ways are there to scale the steps?

If there are 0 steps, there is 1 possibility (you are already done).If there is 1 step, there is 1 possibility (you take one step).If there are n steps, your first choice is either 1 step or 2 steps:Choice 1: the problem now exists for n-1 stepsChoice 2: the problem now exists for n-2 stepsLet f(x) be the number of ways of scaling x steps. You can now say that f(x) = f(x-1) + f(x-2) - the Fibonacci sequence.This is an example of a dynamic programming question - a computer science topic for first-year Cambridge computer scientists, and my first interview question.