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

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!