Сложность: hard
Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.
Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.
Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.
Пример:
Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.
👨💻 Алгоритм:
1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.
2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре.
3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.
😎 Решение:
class Solution {
func stoneGameIII(_ stoneValue: [Int]) -> String {
let n = stoneValue.count
var dp = [Int](repeating: 0, count: n + 1)
for i in stride(from: n - 1, through: 0, by: -1) {
dp[i] = stoneValue[i] - dp[i + 1]
if i + 2 <= n {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
}
if i + 3 <= n {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
}
}
if dp[0] > 0 {
return "Alice"
} else if dp[0] < 0 {
return "Bob"
} else {
return "Tie"
}
}
}Ставь 👍 и забирай 📚 Базу знаний