硬币收集2人游戏

Question

考虑一个正整数值的n个硬币数组和两个玩家player1和player2。每个玩家都会把硬币一圈一圈地转，直到剩下硬币为止。那个带着

最大价值获胜。玩家可以接受的硬币数由变量S最初=1决定，玩家可以从左开始连续地取k个硬币，在1<=k中

<=2*S，当玩家取下k个硬币后，S的值变成最大值(S，k)。此外，还有一个假设，即双方都发挥最优策略。我们必须找到的最大数量

硬币价值，玩家1可以在游戏中获得。

例如:如果输入为3,6,8,5,4，则输出应为12，因为如果player1使用一枚硬币，则播放机2将获得2枚硬币，然后播放机将重取2枚硬币。所以player1

会有3+5+4= 12。

我的想法:我觉得使用动态规划可以找到一些方法，但是我找不到子问题或最优的子结构。情况看上去很复杂。对如何处理这件事有什么想法吗？

Answer 1

该子问题由以下几个方面确定：

• 硬币的数量已经被拿走了。否则，放置:硬币阵列中的指数，下一个硬币可以从哪里取出。
• ，S.

的值

由于可以取的硬币数和S值永远不能超过硬币的数量，所以我们可以用一个大小矩阵来回忆结果。

这一转变对于回忆录来说并不重要:无论是谁的转变，他们都会在同样的状态下拥有同样的机会。因此，如果我们遇到了玩家1的状态，并评估它(最大化硬币价值)，然后遇到相同的状态，但是玩家2要玩，那么先前的结果可以被认为适用于玩家2。

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

对于递归情况，可以播放当前播放器的所有可能移动。对于每个对手，可以通过递归调用获得最佳得分。对于目前的球员来说，最好的一步就是将对手的最佳得分降到最低。

下面是JavaScript中的一个实现。运行此片段将解决问题中的问题，以及1，1，1，1，1，1

​

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]));

​