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 green
Why?? I think I should be grey
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
Wow, nice thanks.