Coins in a Line II

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide the first player will win or lose?

Example Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

思路： 改成从右边拿硬币好理解一些， dp[i]代表从coins[0:i]能拿到的最大价值数。所以核心思想是你要minimize的对手的拿到的价值。 dp[i] = sum[i] - min(dp[i-1], dp[i-2]). 所以又是一个能由i 和 i+1推到出i+2的问题。初始化前两个，然后就可以for loop啦。

http://www.lintcode.com/en/problem/coins-in-a-line-ii/

class Solution(object):
    def coin1(self, nums):
        """
        :type nums: List[int]
        :rtype: boolean
        """
        # reverse the list
        nums = nums[::-1]

        if len(nums)==0:
            return -1

        if len(nums)==1 or len(nums)==2:
            return True

        if len(nums)==3:
            return sum(nums[1:])>nums[0]

        dp = [0]+ [nums[0]]

        for i in range(1,len(nums)):
            cur = sum(nums[:i+1]) - min(dp[-1], dp[-2])
            dp.append(cur)

        return dp[-1] > max(dp[-2], dp[-3])

so = Solution()
print so.coin1([1,2,4])