Участник:Turk0v/Stone Game III

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        stoneValue = stoneValue + [0] * 10
        f = [0] * (n + 10)
        for i in range(n - 1, -1, -1):
            a = stoneValue[i] + min(f[i + 2], f[i + 3], f[i + 4])
            b = stoneValue[i] + stoneValue[i + 1] + min(f[i + 3], f[i + 4], f[i + 5])
            c = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + min(f[i + 4], f[i + 5], f[i + 6])
            f[i] = max(a, b, c)
        a = f[0]
        b = sum(stoneValue) - f[0]
        if a > b:
            return "Alice"
        elif a == b:
            return "Tie"
        else:
            return "Bob"