[LeetCode]动态规划求解博弈问题

博弈论是有趣又有用的知识，可以用来预测在特定的规则下，人们会做出怎样的行为，又会导致怎样的结果。利用博弈论来指导人们的行事法则甚至商业操作，比如著名的囚徒困境就被很好的利用在了商业竞争上。同样，LeetCode也利用博弈论出了几道有意思的题目。

如何解这些博弈类的算法题目呢？如果透过题目表面，理清题目的本质，那么题目可能就是一道数学题。当然了，也可以用正儿八经的算法来求解。本文Jungle将使用动态规划来求解LeetCode上的博弈类问题。

关于动态规划：

• [LeetCode]动态规划及LeetCode题解分析
• 动态规划LeetCode[简单]题全解
• [LeetCode]动态规划之打家劫舍ⅠⅡⅢ
• [LeetCode]动态规划，一举歼灭“股票买卖的最佳时机”问题
• [LeetCode]动态规划，一招团灭最小路径问题

1

292.Nim游戏

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。 示例: 输入: 4 输出: false 解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

分析：面对4的整数倍的人永远无法获胜，你拿N根对手就会拿4-N根，保证每回合共减4根，你永远对面4倍数，直到4。相反，如果最开始不是4倍数，你可以拿掉刚好剩下4倍数根，让他永远对面4倍数。只要剩余的石头数量不是4的倍数，作为先手，你就可以获胜。

bool canWinNim(int n) {
        return n%4 != 0;
    }

那么如何使用动态规划来求解这个问题？

（1）明确数组元素代表的含义

声明一个一维数组dp，类型为bool，dp[i]代表当前还剩i块石头，作为先手是否能够取胜，取胜则dp[i]=true，否则dp[i]=false。

（2）寻找递推关系

当前还剩n块石头时，你可以给对手剩下n-1、n-2、n-3块石头。当n-1、n-2、n-3都必胜时，n必败，所以有如下递推关系：

dp[i] = !(dp[i-1]&&dp[i-1]&&dp[1-3])

（3）数组初始化

dp[1]=true; dp[2]=true;dp[3]=true.

（4）代码，不过超时了

bool canWinNim(int n) {
  if (n == 0){
    return false;
  }
  if (n <= 2){
    return true;
  }
  vector<bool>dp(n + 1, false);

  dp[1] = true;
  dp[2] = true;
  dp[3] = true;
  for (int i = 4; i <= n; i++){
    if (!(dp[i - 1] == true && dp[i - 2] == true && dp[i - 3] == true)){
      dp[i] = true;
    }
  }
  return dp[n];
}

2

1025.除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作： 选出任一 x，满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作，就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。 假设两个玩家都以最佳状态参与游戏。 示例 1： 输入：2 输出：true 解释：爱丽丝选择 1，鲍勃无法进行操作。 示例 2： 输入：3 输出：false 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

分析：因为要满足N%x==0，即x是N的因数。如果N是奇数，那么N的所有因数都是奇数，即x是奇数，那么N-x是偶数。面对偶数的人只需要取x=1，让N-x为奇数即可。所以面对奇数的人无法取胜。

bool divisorGame(int N) {
      return N%2==0;
}

同样，现在我们要使用动态规划来求解此题。

（1）明确数组元素代表的含义

声明一个一维数组dp，类型为bool，dp[i]代表当前数字为i时，爱丽丝是否能够取胜，取胜则dp[i]=true，否则dp[i]=false。

（2）寻找递推关系

若当前数字为i，如果i的约数里面存在让对手输掉的数字，那么爱丽丝面对i就可以取胜。所以递推关系为：

dp[i] = (dp[i-x]==false&&i%x==0)

（3）数组初始化

爱丽丝抽到1则必败，dp[1]=false

（4）代码

bool divisorGame(int N) {
  int *dp = new int[N + 1];
  dp[1] = false;
  for (int i = 2; i <= N; i++){
    for (int x = 1; x<i; x++){
      if (dp[i - x] == false && i%x == 0){
        dp[i] = true;
        break;
      }
    }
  }
  return dp[N];
}

3

877.石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。 亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例： 输入：[5,3,4,5] 输出：true 解释：亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

分析：注意题目要求，这是“偶数堆石子”。也就是说到最后先手和后手那的石子堆数是一样的。所以，先手可以控制拿奇数堆的还是偶数堆的，比如[1,3,5,4]，先手可以先计算，奇数堆的石子总和是1+5=6，小于偶数堆石子总和3+4=7.所以先手就先拿4。总之，先手必胜。

代码：

bool stoneGame(vector<int>& piles) {
    return true;
}

思考：那如果不是偶数堆，而是任意堆或者奇数堆呢？例如[1,5,1]，先手肯定就输了。所以如果是奇数堆，这题就不能这么解了。那么该如何解呢？接下来我们用动态规划来求解此题。

面对一堆石子piles，先手后手轮流从任意一边拿石子。如果我们遍历所有情况，可以列出在每一种情况下先手后手各自获得的石子总数。比如目前石子为piles[]={1,3,6,7}，对于每个区间i~j里，先手后手能够取得的最大石子总数分别为（先手石子总数，后手石子总数），我们可以得到下面表格。

比如区间0~2里的石子{1,3,6}，先手可以拿到6和1，总石子数为7，后手可以拿到总石子数为3，因此在[0,2]位置处的结果为(7,3).

由此我们可以设计一个数据结构来保存每个区间里的先手后手取的石子数量的情况：

class Pair{
public:
  Pair(int a, int b){
    this->first = a;
    this->second = b;
  }
  int first;
  int second;
};

（1）明确数组元素代表的含义

声明一个二维数组dp，类型为Pair，dp[i][j]保存在区间i~j里，先手后手取石子数的情况。

比如{1,3,6,7}这一堆石子，根据上述表格可知

• dp[1][2].first=6：区间1~2里的石子{3,6}，先手最多可以拿到6块石子
• dp[1][2].second=3：区间1~2里的石子{3,6}，后手最多可以拿到3块石子
• dp[0][2].first=7：区间0~2里的石子{1,3,6}，先手最多可以拿到7块石子
• dp[0][2].second=3：区间0~2里的石子{1,3,6}，后手最多可拿到3块石子

我们只需要计算得到dp[0][n-1]，并且判断dp[0][n-1].first是否大于dp[0][n-1].second即可。

（2）寻找递推关系

怎么来得到每一个dp[i][j]的值呢？明确两点：

• 先手拿完石子后，先手就变成了后手，后手就成为了先手；
• 不论谁拿，当前取石子的人只能从最左边取（取piles[ i ]），或者从最右边取（取piles[ j ]）；

基于上述两点：

• 假设先手从最左边取，即取了piles[ i ]，那么下一个人只能在( i+1, j )中取，并且下一个人成为了先手，当前那人成了后手，即：left = piles[ i ] + dp[i+1][j].second
• 假设先手从最右边取，即取了piles[ j ]，那么下一个人只能在( i, j-1 )中取，并且下一个人成为了先手，当前那人成了后手，即：right = piles[ j ] + dp[i][j-1].second

那么先手到底从哪一边取呢？为保证取到最多石子，取上述两种情况的最大值，即dp[i][j].first = max(left, right)

接下来是求石子（i，j）区间里后手可以取到的总石子数，即dp[i][j].secoond，这取决于先手是取的左边还是右边：

• 如果先手取的左边，即piles[ i ]，那么dp[i][j].second = dp[i+1][j].first；
• 如果先手取的右边，即piles[ j ]，那么dp[i][j].second = dp[i][j-1].first；

（3）数组初始化

dp[i][j]表示石子区间i~j，很显然，当i=j时，区间里只有一个石子，肯定先手赢，且先手可以获得i个石子，后手只能得到0个石子。即：

dp[i][i].first = i;
dp[i][i].second = 0;

接下来是如何遍历的问题。因为取石子要么从左边要么从右边取，每取一个，总石子数的长度就减小1，因此我们是遍历石子堆数即长度len。dp[i][i]的情况即是len=1。我们只需要从len=2开始遍历。从下面的图可以看出，对于每一个长度len，i的值从0到n-len；针对每一个i，j=i+len-1。

（4）代码

bool stoneGame(vector<int>& piles) {
  int n = piles.size();
  vector<vector<Pair*>>dp(n, vector<Pair*>(n, NULL));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      dp[i][j] = new Pair(0, 0);
    }
  }
  for (int i = 0; i<piles.size(); i++){
    dp[i][i]->first = piles[i];
    dp[i][i]->second = 0;
  }
  for (int l = 2; l <= n; l++){
    for (int i = 0; i <= n - l; i++){
      int j = l + i - 1;
      int left = piles[i] + dp[i + 1][j]->second;
      int right = piles[j] + dp[i][j - 1]->second;
      if (left>right){
        dp[i][j]->first = left;
        dp[i][j]->second = dp[i + 1][j]->first;
      }
      else{
        dp[i][j]->first = right;
        dp[i][j]->second = dp[i][j - 1]->first;
      }
    }
  }
  int res = dp[0][n - 1]->first - dp[0][n - 1]->second;
  return res >= 0;
}

4

486.预测赢家

给定一个表示分数的非负整数数组。 玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1: 输入: [1, 5, 2] 输出: False 解释: 一开始，玩家1可以从1和2中进行选择。如果他选择2（或者1），那么玩家2可以从1（或者2）和5中进行选择。如果玩家2选择了5，那么玩家1则只剩下1（或者2）可选。所以，玩家1的最终分数为 1 + 2 = 3，而玩家2为 5。因此，玩家1永远不会成为赢家，返回 False。

示例 2: 输入: [1, 5, 233, 7] 输出: True 解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。

分析：这题其实与上一题的思考是一个问题，因此我们可以直接把上一题的代码复制过来。