硬币收集2人游戏

Question

考虑一个由n个正整数值硬币和两个玩家player1和player2组成的数组。每个玩家轮流领取硬币，直到还剩硬币为止。
值最大的一个获胜。玩家可以获得的硬币数量由变量S最初＝1决定，并且玩家可以从左开始连续获得k个硬币，其中1<k
<2*S在玩家拿走k个硬币后，S的值变为max(S，k)。此外，还有一个假设，即两个参与者都采用最佳策略我们必须找到玩家1在游戏中可以获得的最大硬币值

例如：如果输入为[3,6,8,5,4]，则输出应为12，因为如果玩家1获得一枚硬币，玩家2获得两枚硬币，然后玩家1夺回两枚硬币。因此player1
将具有3+5+4=12。
我的想法：我觉得有一些方法可以使用动态规划来实现这一点，但我找不到子问题或最优子结构。情况看起来非常复杂。关于如何处理这个问题，有什么想法吗？

Answer 1

子问题由识别

• 已取走的硬币数量。否则放入：硬币数组中可以从中取出下一个硬币的索引
• S的值

由于可以获得的硬币数量和S的值永远不会超过硬币数量，我们可以使用大小矩阵来存储结果。

转向对记忆来说并不重要：无论转向谁，他们都会在相同的状态下拥有相同的机会。因此，如果我们遇到玩家1的状态并对其进行评估(使硬币价值最大化)，然后后来遇到相同的状态，但玩家2要玩，那么之前的结果可以应用于玩家2。

该算法可以使用递归。当当前玩家可以决定拿走所有剩余的硬币时，就会出现基本情况。当然，这永远是最好的举措。

对于递归情况，可以播放当前玩家的所有可能移动。对于每一个，对手的最佳得分可以通过递归调用得出。当前玩家的最佳移动是对手的最佳得分最小化的移动。

下面是一个JavaScript实现。运行这个片段将解决您在问题中提出的问题，以及[1,1,1,1,11]：

function solve(coins) {
let n = coins.length;
// Preprocessing: for all possibly suffix arrays, calculate the sum of the coins
let sums = coins.slice(); // copy 
for (let i = n - 2; i >= 0; i--) {
sums[i] += sums[i + 1]; // backwards running sum
}
// 2D Array for memoization (dynamic programming)
let dp = []; // n x n matrix, initially filled with -1
for (let i = 0; i < n; i++) dp.push(Array(n).fill(-1));
return recur(0, 1);

function recur(start, s) {
if (n - start <= 2*s) return sums[start]; // base case: take all remaining coins
if (dp[start][s] == -1) { // sub problem was not encountered before
let minOpponentScore = Infinity;
// For each possible move, get best counter move from opponent
for (let k = 1; k <= 2*s; k++) {
// We'll take the move where the best counter move was the worst
minOpponentScore = Math.min(minOpponentScore, recur(start + k, Math.max(k, s)));
}
dp[start][s] = sums[start] - minOpponentScore;
}
return dp[start][s];
}
}
console.log(solve([3,6,8,5,4]));
console.log(solve([1,1,1,1,1,1,1]));