硬币收集 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 拿了 2 个硬币，然后玩家 1 再拿了 2 个硬币。所以玩家 1
将有 3 + 5 + 4 = 12。
我的想法：我觉得可能有一些方法可以使用动态规划来完成，但我找不到子问题或最优子结构。条件看起来很复杂。关于如何处理这个问题有什么想法吗？

Answer 1

子问题被识别为：

已经拿走的硬币数量。否则放置：硬币数组中的索引，可以从中获取下一个硬币。
S的价值

由于可以拿走的硬币数量和S的值永远不会超过硬币数量，我们可以使用大小为的矩阵来记忆结果。

对于memoization而言，轮次并不重要：无论轮到谁，他们在相同的状态下都有相同的机会。因此，如果我们遇到玩家 1 的状态并对其进行评估（最大化硬币价值），然后再遇到相同的状态，但玩家 2 正在玩，那么之前的结果可以应用于玩家 2.

算法可以使用递归。基本情况发生在当前玩家可以决定拿走所有剩余的硬币时。当然，这永远是最好的一步。

对于递归的情况，当前玩家的所有可能走法都可以进行。对于每一个对手的最佳分数可以通过递归调用得出。当前玩家的最佳着法是对手的最佳得分为 minimized.

的着法

这是 JavaScript 中的一个实现。运行此代码段将解决您在问题中提出的问题，以及 [1,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]));

硬币收集 2 人游戏

Coin collection 2 player game

algorithm

dynamic-programming