stone-game.py

# Time:  O(n^2)
# Space: O(n)

# Alex and Lee play a game with piles of stones.
# There are an even number of piles arranged in a row,
# and each pile has a positive integer number of stones piles[i].
#
# The objective of the game is to end with the most stones.
# The total number of stones is odd, so there are no ties.
#
# Alex and Lee take turns, with Alex starting first.
# Each turn, a player takes the entire pile of stones from
# either the beginning or the end of the row.
# This continues until there are no more piles left,
# at which point the person with the most stones wins.
#
# Assuming Alex and Lee play optimally,
# return True if and only if Alex wins the game.
#
# Example 1:
#
# Input: [5,3,4,5]
# Output: true
# Explanation: 
# Alex starts first, and can only take the first 5 or the last 5.
# Say he takes the first 5, so that the row becomes [3, 4, 5].
# If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
# If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
# This demonstrated that taking the first 5 was a winning move for Alex, so we return true.
#
# Note:
# - 2 <= piles.length <= 500
# - piles.length is even.
# - 1 <= piles[i] <= 500
# - sum(piles) is odd.

# The solution is the same as https://leetcode.com/problems/predict-the-winner/description/
class Solution(object):
    def stoneGame(self, piles):
        """
        :type piles: List[int]
        :rtype: bool
        """
        if len(piles) % 2 == 0 or len(piles) == 1:
            return True

        dp = [0] * len(piles);
        for i in reversed(xrange(len(piles))):
            dp[i] = piles[i]
            for j in xrange(i+1, len(piles)):
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1])
        return dp[-1] >= 0