预测C ++的赢家

假设我们有一个分数数组，这些分数是非负整数。第一个玩家从数组的任一端选择一个号码，然后是第二个玩家，然后是第一个玩家，依此类推。每当一个玩家选择一个号码时，该号码将无法用于其他玩家。一直持续到所有分数都被选择为止。得分最高的玩家获胜。因此，如果我们拥有分数数组，则必须预测玩家1是否是赢家。

因此，如果输入类似于[1，5，233，7]，则输出将为True，因为第一个玩家选择了1。然后第二个玩家必须在5到7之间进行选择。玩家选择，第一个玩家可以选择233。最后，第一个玩家的得分(234)比第二个玩家(12)高，因此我们需要返回true，因为第一个玩家可以赢钱。

为了解决这个问题，我们将遵循以下步骤-

• 如果n与1相同，则-

• 返回真

• 定义一个大小为nxn的数组播放器1，定义一个大小为nxn的数组播放器2，以及大小为nx n的和。

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• player1 [i，j]：= -1

• player2 [i，j]：= -1

• 对于初始化j：= 0，当j <n时，更新（将j增加1），执行-

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 如果i与j相同，则-

• 除此以外

• sum [i，j]：= arr [i]

• sum [i，j]：= arr [j] + sum [i，j-1]

• 对于初始化j：= i，当j <n时，更新（将j增加1），-

• 对于初始化长度：= 1，当长度<= n时，更新（将长度增加1），-

• 结束：= i +长度-1

• 如果i + 1 <=结束，则-

• 除此以外

• player2 [i，end]：= sum [i，end]-player1 [i，end]

• player1 [i，end]：= arr [i] +（（如果player2 [i + 1，end]等于-1，则为0，否则为player2 [i + 1，end]）））和arr [end ] +（（如果player2 [i，end-1]与-1相同，则为player2 [i，end-1]））

• player1 [i，end]：= arr [i]

• 对于初始化i：= 0，当i +长度-1 <n时，更新（将i增加1），执行-

• 当player1 [0，n-1]> = player2 [0，n-1]时返回true，否则返回false

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli solve(vector <int> arr, lli n){
      if (n == 1)
         return true;
      lli player1[n][n], player2[n][n], sum[n][n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            player1[i][j] = -1;
            player2[i][j] = -1;
         }
      }
      for (int i = 0; i < n; i++) {
         for (int j = i; j < n; j++) {
            if (i == j) {
               sum[i][j] = arr[i];
            }
            else {
               sum[i][j] = arr[j] + sum[i][j - 1];
            }
         }
      }
      for (int length = 1; length <= n; length++) {
         for (int i = 0; i + length - 1 < n; i++) {
            lli end = i + length - 1;
            if (i + 1 <= end)
               player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1]));
            else
               player1[i][end] = arr[i];
               player2[i][end] = sum[i][end] - player1[i][end];
            }
         }
         return player1[0][n - 1] >= player2[0][n - 1];
      }
      bool PredictTheWinner(vector<int>& nums) {
         return solve(nums, nums.size()) ;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 5, 233, 7};
   cout << (ob.PredictTheWinner(v));
}

输入项

{1, 5, 233, 7}

输出结果

1