How is the dynamic program designed for this problem?

Clarification

Just as the comments point out, the problem is actually missing some requirements. However, from the suggested solution, we can guess that the missing requirement is that the loser of any match will get eliminated immediately and cannot participate in future matches.

Idea

The number of winning matches between two players need to be smaller than or equal to 1. How to approach this? Let's start with n=2 first

1   2
 \ /
  1 (winner)

It is obvious that the winner can win with at most 1 match. How about n=3?

1   2   3
 \ /   /
  1   /
   \ /
    1 (winner)

The winner can win with at most 2 matches in this case, now think about how to find minimal n such that the answer is 3. In fact, we can just combine the above two trees!

1   2   3         Round 1
 \ /   / 
  1   /   4   5   Round 2
   \ /     \ /
    1       4     Round 3
     \     /
      \   /
       \ /
        1 (winner)

Observe how is the above tree a combination of the n=2 and n=3 cases. In Round 3, 1 has won two matches (as n=2) and 4 has won one match (as n=1) so the competition between them is legal. Therefore, it can be seen that to the minimal n such that answer is 4 is

(the minimal n such that the answer is 3) + (the minimal n such that the answer is 2)

This idea can be applied in the same way for larger n. This is where the dp[n] = dp[n - 1] + dp[n - 2] comes from.

Implementation

Once you get the idea, you should be able to understand the c++ code. We get the dp array as follows: (where dp[i] means that the minimal n such that the answer is i)

dp[0] dp[1] dp[2] dp[3] dp[4]
1     2     3     5     8

What we want to do is just find i such that dp[i] <= n < dp[i + 1]. For example, for n=2, i=1; for n=6, i=3, etc

do {
   dp[i] = dp[i - 1] + dp[i - 2];
} while (dp[i++] <= N);

The above code is one way to implement it, although it must not be the most readable code on earth. One could easily achieve the same purpose with two loops.

If you really want to understand why the answer is i - 2, here is a brief explanation. The above loop stops only when n < dp[i++], which is equivalent to n < dp[i]; i++ in c++. But in fact, what we want to find is an element in dp that is smaller than or equal to n, so the value is offset by 1. Also, i++ results in another offset by 1. Therefore, i - 2 would be the answer.

To understand the problem better, let's first list out the answer for small values of N. When there are N players, the maximum number of wins of the winners are as follow:

  N  1  2  3  4  5  6  7  8  9 
ans  0  1  2  2  3  3  3  4  4 

As you can see, for increasing value of N, the answer can only increase. We can now denote dp[i] as the minimum N such that ans >= i, i.e.
dp[0] will be the minimum N such that ans >= 0, which will be N = 1
dp[1] will be the minimum N such that ans >= 1, which will be N = 2
dp[2] will be the minimum N such that ans >= 2, which will be N = 3
dp[3] will be the minimum N such that ans >= 3, which will be N = 5

How to find dp[i] for any i.

As dp[i] denotes the minimum N (number of players) such that ans (number of wins of the winner) is at least i, we will need someone who has won i - 1 match to win one more match. We can do that by matching the player who won i - 1 match with someone who won i - 2 match, this will require the minimum number of players for the winner to win i matches.
Therefore, dp[i] = dp[i - 1] + dp[i - 2]
We need dp[0] = 1 and dp[1] = 2 before calculating because we need 2 elements in dp array to apply the formula above.

Why we need i - 2 in the end

Let's revisit the original question. Now that we have the dp array, how can we find the answer now?
The answer is now same as finding i such that N >= dp[i] and N < dp[i + 1], we can see that there will only be one such i as N can only be between 2 element in the dp array. (refer to the table above)
After the do while loop, the last thing that got executed is dp[i++] <= N which will be false as we exited the loop.
Therefore, we have dp[i - 1] > N and dp[i - 2] <= N now. Now we get the answer i - 2 because it is the only number that satisfy the above requirement.

Why is dp[i - 1] > N?

Because of how i++ works, dp[i++] <= N is actually dp[i] <= N; i++; therefore there will be an extra increment in the end. Therefore dp[i - 1] > N must be satisfied in the end.

Why is dp[i - 2] <= N?

Because in the loop before, we executed the last loop because dp[i++] <= N evaluated to true when i is the final i minus 2, thus continuing the loop.

I believe there are only three ways of understanding this problem (or maybe four if we want to be very creative).

If loser of any match can no longer compete, then above explanation solver the problem and we have to solve recursion for Fibonacci numbers.

In the second way of understanding the statement the player who loses a game can still compete with other contestants. Here we will have a trivial solution, that the winner will be able to win i matches if there are i+1 players at the beginning of the tournament. It is easy to show using recursion that this is true for two players and each next player will win with all previous players.

The third approach comes to my mind from the chess world where in the single round of the tournament all, or all but one player have to play, but in this case I believe there could be some cases where due to problem constraints it would be impossible to create such matching for some round.

And last (very stretched) way is to think that players can play with each other arbitrary number of times. In such case two players can reach any number of wins if they only win every other game.

The last, quoted sentence in Your question also seems to make sense. If we look at i after the process, due to implementation, it will be one greater than the first number greater than the answer, so we should return i-2.

First we want to compute function F, this function takes the number of players as input and its output is the maximum number of games the winner can plays given the requirements of the problem. now I claim F is equivalent with the function P, and function P takes the number of games that the winner played and its output is the minimum number of players that are required to create that many games. i.e.

P(#games) = minimum number of players
F(#players) = maximum number of games

you can consider P like this: maximum number of games that n players can create for winner. from now we work with P

now consider James is the winner and his #games is n. before the last game James played with the Bob according to the requirements of the problem the number of games for James and Bob must be one of the following:

 #games James played = n-1 and #games Bob played=n-1 (state 1)
 #games James played = n-1 and #games Bob played=n-2 (state 2)


            James(#games = n) 
        /                    \
       /                      \
  James(#games = n - 1)  vs   Bob(#games = n - 2) or (#games = n - 1)

some facts until now

• we want to compute P(n) = minimum number of players can create n games or [read it like maximum number of games that those players can create for winner.]
• The players in left and right sub trees are disjoint you can easily verify there is not a player who exist in both sub trees.
• P(n) = P(n-1) + p(n-2) or P(n) = 2P(n-1) we can verify that 2P(n-1) >= P(n-1) + p(n-2) and we want minimum number of players so we consider P(n) = P(n-1) + p(n-2)

for implementation part, I have N players what is the maximum number of games that the winner can play or what is the minimum number of players that can create M wins? it is actually P function

M = 0 --> 1  players needed 
M = 1 --> 2  players needed 
M = 2 --> 3  players needed
M = 3 --> 5  players needed (5 players can create at most 3 games for the winner)

.....

when the computed players exceeds the N(number of available players) we should return previous index. for example if the number of players is 4 when we compute the number of players for M=3 it is 5 and 5 > 4 so we must return 2

To be very simple, if you want a winner that is winning N matches, you need a winner that is winning N - 1 matches and a winner that is winning N - 2 matches, as the number of wins from two competitors needs to be smaller or equal than 1.

So the recurrence relation is simply dp[i] = dp[i - 1] + dp[i - 2].