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