395.Coins in a Line II

1.Description(Medium)

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], returntrue.

Given A =[1,2,4], returnfalse.

2.Code

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)

state: dp[i]表示，在第i个硬币的位置，先出手的人能拿到的最大值。

逻辑是这样的，如果我现在在第i个coin的位置，我拿一个，那么因为对手可以拿1或者2，所以我的value是，
value[i] + dp[i + 2] 或者 value[i] + dp[i + 3]
因为对手是理智的，所以他总是尝试让我的value尽可能小，
于是我拿到grab_one = value[i] + min(dp[i + 2], dp[i + 3])
同样的道理，如果我现在在第i个coin的位置，我拿两个，
于是我拿到grab_two = value[i] + value[i + 1] + min(dp[i + 3], dp[i + 4])。

然后我的策略是尽可能多拿，于是我的dp[i] = max(grab_one, grab_two)。
这道题目，可以初始化只剩下1个，只剩下2个这两种情况，从i = n - 3为下标的地方开始，
因为要考虑到i + 4，所以需要在dp矩阵后面额外再补2个0

动态规划4要素

• State:

  • dp[i] 现在还剩i个硬币，现在当前取硬币的人最后最多取硬币价值

• Function:

  • i 是所有硬币数目

  • sum[i] 是后i个硬币的总和

  • dp[i] = sum[i]-min(dp[i-1], dp[i-2])

• Intialize:

  • dp[0] = 0

  • dp[1] = coin[n-1]

  • dp[2] = coin[n-2] + coin[n-1]

• Answer:

  • dp[n]

可以画一个树形图来解释：

                  [5, 1, 2, 10] dp[4]
        (take 5) /             \ (take 5, 1)
                /               \
        [1, 2, 10] dp[3]         [2, 10] dp[2]
(take 1) /     \ (take 1, 2)  (take 2) / \ (take 2, 10)
        /       \                     /   \
  [2, 10] dp[2]  [10] dp[1]     [10] dp[1] [] dp[0]

也就是说，每次的剩余硬币价值最多值dp[i]，是当前所有剩余i个硬币价值之和sum[i]，减去下一手时对手所能拿到最多的硬币的价值，即dp[i] = sum[i] - min(dp[i - 1], dp[i - 2])

http://www.cnblogs.com/grandyang/p/5864323.html

这道题是之前那道Coins in a Line的延伸，由于每个硬币的面值不同，所以那道题的数学解法就不行了，这里我们需要使用一种方法叫做极小化极大算法Minimax，这是博弈论中比较经典的一种思想，LeetCode上有一道需要用这种思路解的题Guess Number Higher or Lower II。这道题如果没有接触过相类似的题，感觉还是蛮有难度的。我们需要用DP来解，我们定义一个一维数组dp，其中dp[i]表示从i到end可取的最大钱数，大小比values数组多出一位，若n为values的长度，那么dp[n]先初始化为0。我们是从后往前推，我们想如果是values数组的最后一位，及i = n-1时，此时dp[n-1]应该初始化为values[n-1]，因为拿了肯定比不拿大，钱又没有负面额；那么继续往前推，当i=n-2时，dp[n-2]应该初始化为values[n-2]+values[n-1]，应为最多可以拿两个，所以最大值肯定是两个都拿；当i=n-3时，dp[n-3]应该初始化为values[n-3]+values[n-2]，因为此时还剩三个硬币，你若只拿一个，那么就会给对手留两个，当然不行，所以自己要拿两个，只能给对手留一个，那么到目前位置初始化的步骤就完成了，下面就需要找递推式了：

当我们处在i处时，我们有两种选择，拿一个还是拿两个硬币，我们现在分情况讨论：

1. 当我们只拿一个硬币values[i]时，那么对手有两种选择，拿一个硬币values[i+1]，或者拿两个硬币values[i+1] + values[i+2] a) 当对手只拿一个硬币values[i+1]时，我们只能从i+2到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+2] b) 当对手拿两个硬币values[i+1] + values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3] 由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+2]和dp[i+3]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + min(dp[i+2], dp[i+3])

2. 当我们拿两个硬币values[i] + values[i + 1]时，那么对手有两种选择，拿一个硬币values[i+2]，或者拿两个硬币values[i+2] + values[i+3] a) 当对手只拿一个硬币values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3] b) 当对手拿两个硬币values[i+2] + values[i+3]时，我们只能从i+4到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+4] 由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+3]和dp[i+4]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + values[i + 1] + min(dp[i+3], dp[i+4])

综上所述，递推式就有了 dp[i] = max(values[i] + min(dp[i+2], dp[i+3]), values[i] + values[i + 1] + min(dp[i+3], dp[i+4])) 这样当我们算出了dp[0]，知道了第一个玩家能取出的最大钱数，我们只需要算出总钱数，然后就能计算出另一个玩家能取出的钱数，二者比较就知道第一个玩家能否赢了s