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