877. Stone Game

Link

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:

        n = len(piles)

        if n == 2:
            return True

        @cache
        def backtrack(i, j):
            # if only 2 stones , pick largest one
            if j - i + 1 == 2:
                return max(piles[i], piles[j])

            c = 0
            # since player2 always optimize his pick , we can just use smaller one to accumulate
            c = max(c, piles[i] + min(backtrack(i+2, j), backtrack(i+1, j-1)))
            c = max(c, piles[j] + min(backtrack(i, j-2), backtrack(i+1, j-1)))

            return c

        s = backtrack(0, n - 1)

        return s > sum(piles) // 2