LC-1406 Hard LeetCode

1406. Stone Game III

Array Math Dynamic Programming Game Theory

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 63% Topics: Array, Math, Dynamic Programming, 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)
# Space: O(1)

class Solution(object):
    def stoneGameIII(self, stoneValue):
        """
        :type stoneValue: List[int]
        :rtype: str
        """
        dp = [float("-inf")]*3
        dp[len(stoneValue)%3] = 0
        for i in reversed(xrange(len(stoneValue))):
            max_dp, curr = float("-inf"), 0
            for j in xrange(min(3, len(stoneValue)-i)):
                curr += stoneValue[i+j]
                max_dp = max(max_dp, curr-dp[(i+j+1)%3])
            dp[i%3] = max_dp
        return ["Tie", "Alice", "Bob"][cmp(dp[0], 0)]

Solution from kamyu104/LeetCode-Solutions · MIT