Сложность: 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:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -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"
elif dp[0] < 0:
return "Bob"
else:
return "Tie"
Ставь 👍 и забирай 📚 Базу знаний