coins-in-a-line-ii.py

# coding: utf-8

class Solution:
    # @param values: a list of integers
    # @return: a boolean which equals to True if the first player will win
    def firstWillWin(self, values):
        # write your code here
        # score[i]表示从i开始到end能获取的最大值。
        if len(values) <= 2:
            return True
        score = [0] * (len(values) + 1)
        score[-1] = 0
        score[-2] = values[-1]
        score[-3] = values[-2] + values[-1]
        score[-4] = values[-3] + values[-2]
        for i in xrange(len(values) - 4, -1, -1):
            # 拿1个后，对方取1个或2个的情况。
            score[i] = values[i] + min(score[i + 2], score[i + 3])
            # 拿2个后，对方取1个或2个的情况。
            score[i] = max(score[i], values[i] + values[i + 1] + min(score[i + 3], score[i + 4]))
        return True if score[0] > (sum(values) - score[0]) else False

# medium: http://lintcode.com/zh-cn/problem/coins-in-a-line-ii/