预测C ++的赢家
假设我们有一个分数数组，这些分数是非负整数。第一个玩家从数组的任一端选择一个号码，然后是第二个玩家，然后是第一个玩家，依此类推。每当一个玩家选择一个号码时，该号码将无法用于其他玩家。一直持续到所有分数都被选择为止。得分最高的玩家获胜。因此，如果我们拥有分数数组，则必须预测玩家1是否是赢家。
因此，如果输入类似于[1，5，233，7]，则输出将为True，因为第一个玩家选择了1。然后第二个玩家必须在5到7之间进行选择。玩家选择，第一个玩家可以选择233。最后，第一个玩家的得分(234)比第二个玩家(12)高，因此我们需要返回true，因为第一个玩家可以赢钱。
为了解决这个问题，我们将遵循以下步骤-
如果n与1相同，则-
返回真
定义一个大小为nxn的数组播放器1，定义一个大小为nxn的数组播放器2，以及大小为nxn的和。
对于初始化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