Coin Game II

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。计算两个人分别拿到的硬币总价值,价值高的人获胜。

请判定 第一个玩家 是输还是赢?

样例

给定数组 A = [1,2,2], 返回 true.
给定数组 A = [1,2,4], 返回 false.

Solution

state

DP[i]表示从i到end能取到的最大value

function

当我们走到i时,有两种选择

  1. 取values[i]
  2. 取values[i] + values[i+1]

我们取了values[i],对手的选择有 values[i+1]或者values[i+1] + values[i+2] 剩下的最大总value分别为DP[i+2]或DP[i+3], 对手也是理性的所以要让我们得到最小value。

所以 value1 = values[i] + min(DP[i+2], DP[i+3])

我们取了values[i]和values[i+1] 同理

value2 = values[i] + values[i+1] + min(DP[i+3], DP[i+4])

最后

DP[I] = max(value1, value2)

Code

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):
        if not values:
            return True
        length = len(values)
        dp = [0 for i in range(length)]
        dp[length-1] = values[length-1]
        dp[length-2] = values[length-1] + values[length-2]
        for i in range(length - 3, -1, -1):
            if i + 4 <= length - 1:
                a = dp[i+4]
            else:
                a = 0
            if i + 3 <= length - 1:
                b = dp[i+3]
            else:
                b = 0
            if i + 2 <= length - 1:
                c = dp[i+2]
            else:
                c = 0

            v1 = values[i] + min(c, b)
            v2 = values[i] + values[i+1] + min(a,b)
            dp[i] = max(v1,v2)

        total = 0
        for j in range(length):
            total += values[j]

        second = total-dp[0]
        if dp[0] > second:
            return True
        else:
            return False