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.

I believe the recurrence is: DP[x][y] = # of ways to reach stair x using 3 step move y times

DP[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 ;)

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

What are u printing in the answer ?

number of ways % mod

sum of dp[n][i] i from 0 to B ?

no, i get the solution now i was doing something wrong. I was printing dp[A][B] tho

yeah I thought you might be printing dp[n][B]

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

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.

No wonder you are greenWhy?? I think I should be grey

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 .

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

My top down implementation

Thank you for the solution. Got it now.

Wow, nice thanks.

Can you share the problem link?

Hi, I think you can easily approach this problem with dynamic programming approach, you can check the climbing stairs detailed solution