There is a stair with N step. You can jump either 1 step or 2 steps at time. How many different ways do you want to reach the top?

Solution

N = 1 --> 1

N = 2 ,, 1s+1s, 2s -> 2

N = 3 , 1s+1s+1s, 2s+1s, 1s+2s -> 3

N = 4, 1s+1s+1s+1s, 1s+1s+2s, 1s+2s+1s, 2s+1s+1s, 2s+2s -> 5

N = 5, 1s+1s+1s+1s+1s, 1s+1s+1s+2s, 1s+1s+2s+1s, 1s+2s+1s+1s, 2s+1s+1s+1s, 1s+2s+2s, 2s+1s+2s, 2s+2s+1s = 8

so and why?

I got this one during the interview, and I must say the answer is rather surprising.

ReplyDeleteThanks for the good blog,

Lukasz.

Fibonacci series...

ReplyDeleteFor explanation read http://tech-queries.blogspot.com/2011/07/fit-12-dominos-in-2n-strip.html