A stair flight has 10 steps. A kid can move in jumps of 1, 2 or 3 steps. Assume the kid starts on the floor (step 0), and always has to end in step 10 because there is a door that needs to be open. In how many possible ways can the kid reach the last step?
For example, the kid may do 8 "one step" jumps, and 1 "two steps" jump. There would be 9 possible ways of reaching step 10 this way. (211111111,121111111, ...etc...)
The approach I took is that considering the three types of jump:
- j1 : 1 step.
- j2 : 2 steps.
- j3 : 3 steps.
I found these 12 possible ways of doing the stair in 10 steps:
j1x10 j2x0 j3x0 j1x8 j2x1 j3x0 j1x7 j2x0 j3x1 j1x6 j2x2 j3x0 j1x5 j2x1 j3x1 j1x4 j2x3 j3x0 j1x4 j2x0 j3x2 j1x3 j2x2 j3x1 j1x2 j2x4 j3x0 j1x1 j2x0 j3x3 j1x0 j2x2 j3x2 j1x0 j2x5 j3x0
The first possibility would be ten jumps by doing j1*10 j2*0 j3*0, that would be 10!/10! = 1 possibility.
Next possibility would be nine jumps by doing
j1x8 j2x1 j3x0, 9!/(8!*1!) = 9 possibilities.
Next would be eight jumps by doing
j1x6 j2x2 j3x0, 8!/(6!*2!) = 28 possibilities.
The sum of all the possibilities would be the result.
Even if the result is right, I found the approach very rough, and difficult to scale to a 100 steps stair flight. Which would be a better approach for this problem that can be applied to a 100 steps stair?