Unable to solve this catalan number problem

Hey everyone!

So I got stuck in this problem from tutorial i found that it has to be solved using catalan number thing. But since this problem is showing a recursive pattern so i was thinking if we could do it by dynamic programing/ recursion.

Please help, I am new to in CP

Let’s define dp[P][F] as the number of ways, such that Phineas is at position P, and Ferb is at position F. We finish the game when both Phineas and Ferb are at position N+1, so we need to calculate dp[N+1][N+1].

Let’s try to figure out our recurrence and base cases.

Let’s see from which states can we get to state P, F:

  • It was Phineas who took the previous move, so the previous state was dp[P-1][F].
  • It was Ferb who took the previous move, so the previous state was dp[P][F-1].

That’s actually all of the previous states where we can reach P, F. The current state dp[P][F] is just the sum of all these previous states.

Now let’s figure out our base cases:

  • When N = 1, there is exactly one way they can play an empty game, so dp[1][1] = 1.
  • You can’t really step on any boxes with position < 1, so dp[P][F] = 0 for P < 1 or F < 1.
  • Ferb’s position cannot be greater than Phineas’, so dp[P][F] = 0 for F > P.

And we’ve covered all of the base cases. Now we can implement these formulas and calculate every possible answers.

1 Like

Really Thanks Man!