Блог пользователя CP_Sucks

Автор CP_Sucks, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

»
4 года назад, # |
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...20

My top down implementation