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时,有两种选择
- 取values[i]
- 取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