DP Problem Stair Case With a Twist

Revision en1, by CP_Sucks, 2019-10-09 05:29:56

I recently gave a test in which there was this classic Dp problem.

Given some stairs you need to reach Ath stair and you are currently standing on ground (0th stair)

You can do 3 things take 1step,2step,3step

But catch is you can take 1,2 step as many times as you want but the number of time you can make 3step move is only B.

Now we need to tell how many ways there are to reach the Ath stair.

Give Answer mod 1e9 + 7

Constraints A <= 1e5 , B <= 20

I was not able to do it, if someone could provide a working code for it that would be great.

Thanks in advance.

Tags #dp, #interviews


  Rev. Lang. By When Δ Comment
en1 English CP_Sucks 2019-10-09 05:29:56 620 Initial revision (published)