博弈类DP

思路

博弈类问题的套路一般比较明显，就是两个人在玩游戏，无非是看谁能达到最后一步move或者看谁能取的价值总和最大。而要理解博弈类问题我们就要理解一句话和一个定义。这句话是assume strategy is the best but luck is the worst。底下有详细的解释。而定义则是DP solution的状态定义，这是解决博弈类问题的关键。对于博弈类问题，我们的定义如下，在剩余的n件物品里面，当前选手作为先手（该当前选手move了），是否能够获胜／所能取得的最大价值总和。如果只从一边取，那么状态可以定义为一维数组，如果可以从两边取，那么又涉及到区间类DP的思想，我们要使用二维矩阵定义。

步骤

因为是DP问题，所以我们还是follow DP四要素

• 状态定义，主要是看两点，如何表示剩余物品，状态的含义是true/false还是价值
• 初始化，因为这里我们都使用递归解决，所以初始化都在递归里了，这里不用考虑
• 状态转移方程，参考strategy is the best, luck is the worst
• return 结果

题型

博弈类DP主要有两种题型：

• 取不取得到。这种类型的题目我们只需要考虑A->B两步move，核心是只要B有一种情况会输，A就会让B输。换句话说，B要想赢，必须每种情况都赢才行。
• 取到价值总和最大。这种类型的题目我们需要考虑A->B->A三步move，原因是这里我们的状态定义是取得的最大价值总和，考虑A我们可以知道A当前move取到的价值，考虑A->B可以知道B在剩余物品里可以获得的最大价值总和。但到这一步我们还是不知道A在剩余物品里所能获得的最大价值总和，也就是我们的状态定义。所以我们要考虑A->B->A，这样我们可以得到A在剩余物品里可以获得的最大价值总和。而逻辑则是strategy is the best, luck is the worst。也就是针对A当前的每种情况，在B可以掌控的情况里，B一定会让A拿走最少的，但是在所有A可以掌控的情况里，A又可以挑选最大的。

题目

取不取得到

• Leetcode 294. Flip Game II
• Lintcode 394. Coins in a Line

取到价值总和最大

• Leetcode 375. Guess Number Higher or Lower II
• Lintcode 395. Coins in a Line II
• Lintcode 396. Coins in a Line III