Coins in a Line III

Question

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

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

Example

Given array A = [3,2,2], return true.

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

Given array A = [1,20,4], return false.

Challenge Follow Up Question:

If n is even. Is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?

Thoughts

同2的分析

follow up怎么做？

Solution

time lime exceeds...

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)
        #state
        #dp[i][j] means the maximum value we can get for values[i:j]
        #function
        dp = [[0 for i in range(length)] for j in range(length)]
        total = 0
        for k in range(length):
            dp[k][k] = values[k]
            total += values[k]
        for start in range(length-1, -1, -1):
            for end in range(start+1, length):
                #dp[start+2][end]
                if start + 2 <= length - 1:
                    a = dp[start+2][end]
                else:
                    a = 0
                #dp[start+1][end-1]
                if start + 1 <= length - 1 and end - 1 >= 0:
                    b = dp[start+1][end-1]
                else:
                    b = 0
                #dp[start][end-2]
                if end-2 >= 0:
                    c = dp[start][end-2]
                else:
                    c = 0
                value1 = values[start] + min(a,b)
                value2 = values[end] + min(b,c)
                dp[start][end] = max(value1, value2)

        if dp[0][length-1] > total / 2:
            return True
        else:
            return False