Fog Creek Software
Discussion Board




stairs

This one is not too hard.
You have N stairs you want to climb. At each step you either
climb one stair, or two stairs. How many total ways are there to climb the N stairs.

john11
Monday, April 08, 2002

Well, the most obvious way to figure this out is to start with the N=1 case, then N=2, and so on, and hope some inductive pattern appears.

For N=1, P(N) (the number of paths up N stairs)=1.  P(2)=2.  You have two first choices - one step or two.  After that, you have either 0 or 1 step left, so there are no more choices left.

For N=3, you can take one step and have two left, or two steps and have one left.  The pattern should be clear by now.  With two steps left, you have the same number of choices as when N=2.  With one left, it's the same as when N=1.

In general, you get P(N) by adding P(N-1) and P(N-2).  Since you start with a different number of steps for P(N-1) and P(N-2), you can be sure that those two sets of paths don't have any paths in common.

I don't know of any way to compute P(N) without using an iterative formula, but most readers should by now recognize subsequent P values as the Fibonacci series.

Paul Brinkley
Monday, April 08, 2002

*  Recent Topics

*  Fog Creek Home