Given n stairs, how many number of ways can you climb if u use either 1, 2 or 3 at a time?
When you find any difficult problem first step is to reduce it to very small problem with example
Consider 3 steps. you can take only one at a time. Then number of ways are 1: ie {(1,1,1)}
Consider 3 steps. you can take 1 or 2 at a time Number of ways : 3 ie : {(1,2),(2,1),(1,1,1)}
Consider 4 steps. you can take 1 or 2 at a time Number of ways : 5
ie {(1,1,1,1), (1,2,1),(1,1,2),(2,1,1),(2,2)}
Consider 4 steps. you can take 1 or 2 at a time Number of ways : 5
ie {(1,1,1,1), (1,2,1),(1,1,2),(2,1,1),(2,2)}
See carefully 2,3,5......
This makes Fibonacci series
because If we are at Nth step then to reach at bottom (same as climbing) at each step we can decide whether to take N-1 or N-2 step and at each decision further option keeps open.
so Function if we can take 1 or 2 is
so Function if we can take 1 or 2 is
F(n) = F(n-1) + F(n-2) ;
Similarly if we can take three steps 1,2 or 3
F(n) = F(n-1) + F(n-2) + F(n-3) ;
