How do you solve the climbing stairs problem, and what is the recurrence?
You work out how many ways there are to reach each step, and the answer for a step is the sum of the answers for the step below it and the step below that.
the step the ways
----------- ----------
1 1
2 2
3 3
4 5
5 8
6 13
And the recurrence is this. The number of ways to reach step n is the number of ways to reach step n minus one plus the number of ways to reach step n minus two. Because the last move into step n was either a one step from n minus one or a two step from n minus two.
And that is the Fibonacci sequence with the numbers moved along. The numbers are one, two, three, five, eight and thirteen. So the climbing stairs problem is Fibonacci wearing a different hat.
the step the ways the Fibonacci number
----------- ---------- -------------------
1 1 2
2 2 3
3 3 5
4 5 8
And the base cases are worth getting right. There is one way to get to step one and one way to get to step two, so the answers are one and one in the version where the count is the number of routes. The other common version counts the empty staircase as one route, and then the answers start at one and one as well and step three is two.
And there is a way to write the answer in closed form, which is worth knowing about. It is the Fibonacci number at position n plus one, and there is a formula for that with the square root of five in it. That formula is a curiosity and not something you write in an interview.
And the complexity depends on which version you use. The plain recursion is exponential. The version with a table or with a loop is O of n for the time.
So the rule to remember is this. The answer for step n is the answer for n minus one plus the answer for n minus two.
The next two questions in this topic show the loop version and the table version.