Coins in a Line II

Question

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.

Thoughts

state

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

function

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

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

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])

2. 我们取了values[i]和values[i+1] 同理 value2 = values[i] + values[i+1] + min(DP[i+3], DP[i+4])

最后

DP[I] = max(value1, value2)

Solution

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
        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