Standard DP question


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,

  1. 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