java - 针对这个问题的动态程序是如何设计的呢？

Question

我正在解决这个问题:Maximum games played by winner 。为了方便起见，在此引用:

有 N 位玩家正在参加锦标赛。我们需要找到获胜者可以玩的最大游戏数。在本次锦标赛中，只有两名选手的比赛数之差不超过一局，才可以进行对战。

输入: N = 4 输出: 2

Maximum games winner can play = 2
Assume that player are P1, P2, P3 and P4
First two pairs will play lets (P1, P2) and 
(P3, P4). Now winner of these two games will 
play against each other, making total games
played by winner = 2

我的困惑在于下面解释的方法:

We can solve this problem by first computing minimum number of players required such that the winner will play x games. Once this is computed actual problem is just inverse of this. Now assume that dp[i] denotes minimum number of players required so that winner plays i games. We can write a recursive relation among dp values as, dp[i + 1] = dp[i] + dp[i – 1] because if runner up has played (i – 1) games and winner has played i games and all players against which they have played the match are disjoint, total games played by winner will be addition of those two sets of players. Above recursive relation can be written as dp[i] = dp[i – 1] + dp[i – 2]

这是我的理解。

Let's say 4 players p1, p2, p3, p4.

The games are
Game 1: (p1, p2) winner p1
Game 2: (p3, p4) winner as p3
Game 3: (p1,p3) winner as p1

The winner is p1 and the runner is p3. 

在第 1 场比赛中，跑者 p3 打了 0 场比赛。所以 dp[i-1] = 0。获胜者玩了 1 场比赛，所以 dp[i] = 1。所以 dp[2] = 1 + 0 = 1。我完全困惑如何理解这种解决方案。

最后解决方案是这样的:

int maxGameByWinner(int N)
{
  int[] dp = new int[N];
          
  // for 0 games, 1 player is needed
  // for 1 game, 2 players are required
  dp[0] = 1;   
  dp[1] = 2;
              
  // loop until i-th Fibonacci number is 
  // less than or equal to N
  int i = 2;
  do {
    dp[i] = dp[i - 1] + dp[i - 2];
  } while (dp[i++] <= N);
          
  // result is (i - 2) because i will be
  // incremented one extra in while loop
  // and we want the last value which is
  // smaller than N, so one more decrement
  return i - 2;
}

我也不清楚这是什么意思// result is (i - 2) because i will be incremented one extra in while loop and we want the last value which is smaller than N, so one more decrement return (i - 2);

Answer 1

澄清

正如评论所指出的，这个问题实际上是缺少一些需求。然而，从建议的解决方案中，我们可以猜测，缺少的要求是任何一场比赛的失败者将立即被淘汰，并且不能参加以后的比赛。

想法

两名玩家之间获胜的比赛次数必须小于或等于1。如何处理这个问题？让我们从 n=2 开始首先

1   2
 \ /
  1 (winner)

很明显，获胜者最多可以赢得 1 场比赛。怎么样n=3 ？

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

在这种情况下，获胜者最多可以赢得 2 场比赛，现在考虑如何找到最小 n这样答案就是 3 。事实上，我们可以将上面的两棵树组合起来!

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

观察上面的树是如何组合 n=2 的和n=3案例。在第三轮中，1赢得了两场比赛(如 n=2 )和 4赢得了一场比赛(如 n=1 )，因此他们之间的竞争是合法的。因此，可以看出，最小n这样答案是 4

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

这个想法可以以同样的方式应用于更大的 n 。这就是dp[n] = dp[n - 1] + dp[n - 2]的地方来自。

实现

一旦你明白了这个想法，你应该能够理解 C++ 代码。我们得到dp数组如下:(其中 dp[i] 表示最小 n 使得答案为 i )

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

我们想要做的就是找到 i 使得 dp[i] <= n < dp[i + 1] 。例如，对于 n=2 , i=1 ;对于 n=6 , i=3等

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

上面的代码是实现它的一种方法，尽管它不一定是地球上最可读的代码。通过两个循环可以轻松实现相同的目的。

如果你真的想了解为什么答案是 i - 2 ，这里简单解释一下。上述循环仅在 n < dp[i++] 时停止。 ，相当于n < dp[i]; i++在c++中。但实际上我们要找的是dp中的一个元素小于或等于 n ，因此该值偏移 1。此外，i++导致另一个偏移 1。因此，i - 2这就是答案。