Coins in a Line II

题目

ref： Coins in a Line II

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.

方法一

好酷的方法~这个更厉害，网上都没有

dp[i]存的是，在第i位上第一个选手比第二个选手多的得分（可以为负数）

状态转移方程是dp[i] = max{values[i] - dp[i+1], values[i] + values[i+1]-dp[i+2]}

初始化是dp[len - 1] = values[len - 1], dp[len - 2] = values[len - 2]

代码是

方法二

有个博客说的挺好的，比九章自己写的清楚

意思是这样的： 如果我们在第i个位置，那么我们有两种选择，我们要选取里面更大的

• 我们只拿一个values[i]，那么对方也是很机智的，他会试图给我们最差的结果，会选择拿一个[i+1]或者两个[i+1]&[i+2]，试图给我们留更小的值，所以我们自动拿到了dpi+2和dpi+3中比较小的那个，此时dp[i]_1 = values[i] + min{dp[i+2], dp[i+3]};

• 我们拿了两个数, values[i]&values[i+1]，和上一种可能里一样，机智的对手会给我们剩下dp[i+3]和dp[i+4]里比较小的那个， 此时dp[i]_1 = values[i]+values[i+1]+min{dp[i+3], dp[i+4]};

所以结果是dp[i] = max{dp[i]_1, dp[i]_2}

• 我们可以想象是从右往左推导，因为前面的结果需要确定的后面的结果

• 初始化的问题：首先我们可以人工分析出，如果有两个及以下的结果，就是都选了，如果有三个数的时候，就从左往右选前两个，因为就算不能赢也尽量给对手少点。但是到四个的时候，这个就不一定了，要根据具体的数字分析，我们不能强行初始化了。但是dp的时候又需要用到dp[i+4]，所以只能多加一格，初始化成0，来辅助dp

代码