Can anyone pls help me to solve this question?
use fibonacci recurrence relation to solve this .
1 Like
Let dp[i] denote the number of ways to get on to the i th stair.
assume i>3, (you can hardcode for i=1,2,3)
for getting onto the i th stair, he has three possiblities for the last step,
- he might be on (i-1)st step and climbed one stair
2)he might be on (i-2)st step and climbed two stairs
3)he might be on (i-3)st step and climbed three stairs
and all these 3 ways are different with respect to the last step
so, dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
answer is dp[n] which can be found iterating from 1 to n
1 Like
Thanks…