LC-1140 Medium LeetCode

1140. Stone Game II

Array Math Dynamic Programming Prefix Sum Game Theory

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 73% Topics: Array, Math, Dynamic Programming, Prefix Sum, Game Theory

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n*(logn)^2)
# Space: O(nlogn)

class Solution(object):
    def stoneGameII(self, piles):
        """
        :type piles: List[int]
        :rtype: int
        """
        def dp(piles, lookup, i, m):
            if i+2*m >= len(piles):
                return piles[i]
            if (i, m) not in lookup:
                lookup[i, m] = piles[i] - \
                               min(dp(piles, lookup, i+x, max(m, x))
                                   for x in xrange(1, 2*m+1))
            return lookup[i, m]

        for i in reversed(xrange(len(piles)-1)):
            piles[i] += piles[i+1]
        return dp(piles, {}, 0, 1)

Solution from kamyu104/LeetCode-Solutions · MIT