Leetcode 909 Solution

This article provides solution to leetcode question 909 (stone-game)
Categories:
Tags:
Access this page by simply typing in "lcs 909" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/stone-game

Solution

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        s = [[0] * n] * n
        a = [[0] * n] * n



        for i in range(n):
            curr = 0
            for j in range(i, n):
                curr += piles[j]
                s[i][j] = curr



        for i in range(n):
            a[i][i] = piles[i]



        for d in range(1, n):
            for i in range(n - d):
                j = i + d
                a[i][j] = max(piles[i] + s[i + 1][j] - a[i + 1][j], piles[j] + s[i][j - 1] - a[i][j - 1])



        return a[0][n - 1] * 2 > s[0][n - 1]