# Coins in a line III

• Two players and one line of coins. Each player can either pick one or two coins from left side, or one or two coins from right side. The player who ends up getting the highest value wins. Return whether the first player (pick first) can win.

e.g., coins [1,2,3,4,5,6,7,1,2,3]. First player can win.
e.g., coins[1,1,10,1,1]. First player cannot win.

``````def firstWillWin(coins):
if len(coins) <= 2:
return len(coins) != 0
# max values first can get from coins[i:j + 1]
dp = [[0 for j in range(len(coins))] for i in range(len(coins))]
for i in range(len(coins) - 1, -1, -1):
for j in range(i, len(coins)):
if i + 1 >= j:
dp[i][j] = sum(coins[i:j + 1])
elif i + 3 >= j:
dp[i][j] = max(sum(coins[i:i + 2]), sum(coins[j - 1:j + 1]))
else:
# pick left one
dp[i][j] = coins[i] + min(dp[i + 2][j], dp[i + 3][j], dp[i + 1][j - 1], dp[i + 1][j - 2])
# pick left two
dp[i][j] = max(dp[i][j], sum(coins[i:i + 2]) + min(dp[i + 3][j], dp[i + 4][j], dp[i + 2][j - 1], dp[i + 2][j - 2]))
# pick right one
dp[i][j] = max(dp[i][j], coins[j] + min(dp[i + 1][j - 1], dp[i + 2][j - 1], dp[i][j - 2], dp[i][j - 3]))
# pick right two
dp[i][j] = max(dp[i][j], sum(coins[j - 1:j + 1]) + min(dp[i + 1][j - 2], dp[i + 2][j - 2], dp[i][j - 3], dp[i][j - 4]))
print dp
return dp[0][len(coins) - 1] > sum(coins) - dp[0][len(coins) - 1]

coins = [1,2,3,4,5,6,7,1,2,3]
print firstWillWin(coins)
coins = [1,1,1,1,1,1,1,1,1,1]
print firstWillWin(coins)
coins = [1,1]
print firstWillWin(coins)
coins = [1,1,1,1]
print firstWillWin(coins)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.