### once_twice's blog

By once_twice, history, 8 months ago, ,

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.

• +5

 » 8 months ago, # |   +1 I believe the recurrence is: DP[x][y] = # of ways to reach stair x using 3 step move y timesDP[i + 1][j] += DP[i][j]; DP[i + 2][j] += DP[i][j]; DP[i + 3][j + 1] += DP[i][j];Don't forget modulo ;)
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I tried something similiar but couldn't get it to work. If you could write code that would be great. Because i think there are more cases in transition of dp. That was the part i couldn't think of. But i think your solution is quite reasonable. Thanks
•  » » » 8 months ago, # ^ |   0 What are u printing in the answer ?
•  » » » » 8 months ago, # ^ |   0 number of ways % mod
•  » » » » » 8 months ago, # ^ | ← Rev. 3 →   0 sum of dp[n][i] i from 0 to B ?
•  » » » » » » 8 months ago, # ^ |   0 no, i get the solution now i was doing something wrong. I was printing dp[A][B] tho
•  » » » » » » » 8 months ago, # ^ |   0 yeah I thought you might be printing dp[n][B]
 » 8 months ago, # |   +7 Btw if the contest is over why are you asking for working code instead of approach. Looks suspicious. I suppose it's from an ongoing Contest and all you care is about getting it accepted
•  » » 8 months ago, # ^ |   +2 No wonder you are green. My friend it's from a interviewbit placement test i gave yesterday. DM me if you want more details. Also i tried this question for long time in test(1 hour) and couldn't reach a solution so needed a working code so that i could understand properly how states and transitions and all base cases were.
•  » » » 8 months ago, # ^ |   +8 No wonder you are greenWhy?? I think I should be grey
 » 8 months ago, # |   0 At each step starting from 0 calculate no of ways to go there with 0 use of 3;1 use of 3;2 use of three...20 use of three .
 » 8 months ago, # | ← Rev. 2 →   +6 Let's solve this problem with a dynamic approach. dp[A][B] is the number of ways to reach stair 0 from the stair A using at most B triple steps. Then there is two cases, if B > 0, then dp[A][B] = dp[A-1][B] + dp[A-2][B] + dp[A-3][B-1]. And if B = 0, our dp will be the same, except that the last part won't be counted. And the base case is, obviously, dp[0][j] = 1 for all j in the range 0...20My top down implementation
•  » » 8 months ago, # ^ |   0 Thank you for the solution. Got it now.
•  » » 8 months ago, # ^ |   0 Wow, nice thanks.
 » 8 months ago, # |   0 Can you share the problem link?