Q-: https://www.codechef.com/problems/JAM11

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…