CP_Sucks's blog

DP Problem Stair Case With a Twist
By CP_Sucks, history, 5 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      No wonder you are green

      Why?? I think I should be grey

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply