考慮具有正整數值的 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。
我的想法：我覺得可以使用動態規劃來實作它，但是我找不到子問題或最優子結構。條件看起來非常復雜。關于如何解決這個問題的任何想法？
uj5u.com熱心網友回復：
子問題通過以下方式識別：
- 已經拿走的硬幣數量。否則放入：coins 陣列中的索引，可以從中取出下一個硬幣。
- S 的值。
由于可以取出的硬幣數量和 S 的值永遠不會超過硬幣數量 ??，我們可以使用大小為 ?? 的矩陣來記憶結果。
輪到記憶并不重要：無論輪到誰，他們都會在相同的狀態下擁有相同的機會。因此，如果我們遇到玩家 1 的狀態并對其進行評估（最大化硬幣價值），然后遇到相同的狀態，但玩家 2 可以玩，那么可以將先前的結果應用于玩家 2。
該演算法可以使用遞回。基本情況發生在當前玩家可以決定拿走所有剩余硬幣時。當然，這永遠是最好的舉措。
對于遞回情況，可以播放當前玩家的所有可能移動。對于每個對手的最佳分數可以通過遞回呼叫來獲得。當前玩家的最佳移動是最小化對手的最佳分數的移動。
這是 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]));轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359107.html
下一篇：斐波那契記憶回傳串列從0到N