问题描述

给你一组排成一排的数字卡片 cards 。玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家每次只能从 cards 的任意一端取一张卡片（即，cards[0] 或 cards[cards.length - 1]），取到的卡片将会从 cards 中移除。玩家选中的卡片数字将会加到他的得分上。当卡片全部被取走后，游戏结束。假设玩家都绝顶聪明，每一步取法都会使自己的分数最大化 。请返回两个玩家最终得分的较大值。

本题属于博弈问题。博弈论是一门深奥的逻辑科学，博主不敢就本题对博弈论妄做分析，有兴趣的读者可移步博弈论入门。

力扣提交地址：预测赢家。

此题解由本人原创，可以自信的说，这是最简单的解法没有之一。

暴力递归

读完题目后可以迅速产生下面两个想法：

1. 只能从 cards 的两端取卡片？好，那我们将 cards 设计成双端队列 deque ，卡片只能从队列的头部和尾部获得。
2. 有两个玩家，且分先后手？好，那我们用两个函数 f 和 g 分别表示先后手，函数返回值含义为：该玩家在 cards 中能够取得的最大得分 。

基于上面两点，初步设计出以下函数：

int f(deque<int> cards);
int g(deque<int> cards);

游戏的过程是：先手->后手->先手->后手… 所以我们会进行下面的尝试：

int f(deque<int> cards)//先手
{
    //......先手拿牌
    g(cards);//然后后手
    //......
}
int g(deque<int> cards)//后手
{
    //......后手拿牌
    f(cards);//然后先手
    //......
}

f() 和 g() 函数相互嵌套，从而能够正确地模拟游戏顺序。让我们继续模拟这个游戏过程。

玩家每一步只有两个选择，要么选队首的卡片，要么选队尾的卡片 。有了之前题目的经验，显然我们需要对这两种情况都进行尝试，然后选择较大值。所以进一步做如下尝试（代码框架）：

int f(deque<int> cards)
{
    //......
    //情况1:选队首
    int left = cards.front();//选择队首的卡片
    cards.pop_front();//取走
    g(cards);//然后轮到后手
    //......
    
    //情况2:选队尾
    cards.push_front(left);//复原cards
    int right = cards.back();//选择队尾的卡片
    cards.pop_back();//取走
    g(cards);//然后轮到后手
    //......
    //然后返回先手较大值,具体怎么返回暂不清楚
}
//g()同理

目前我们的思路都是非常自然的。现在的问题是，如何返回较大值？像下面这样？

int f(deque<int> cards)
{
    //.....
    int left = cards.front();//选择队首的卡片
    cards.pop_front();//取走
    int score1 = left + g(cards);//然后轮到后手
    //......
    cards.push_front(left);//复原cards
    int right = cards.back();//选择队尾的卡片
    cards.pop_back();//取走
    int score2 = right + g(cards);//然后轮到后手
    return max(score1, score2);
}

有点像那么回事，但显然有问题：g() 函数返回的是后手在 cards 中取得的最大值 ，而上面的 left 和 right 是当前先手取得的分数，将后手取得的最大值与先手当前取得的分数相加，这是什么意思？不伦不类，显然没有意义。要相加也应该是加上先手后续取得的最大值，得到先手的总得分 ，如下：

int score1 = left + f(cards);
int score2 = right + f(cards);

可是如果这样的话，就是先手一直取牌，正常的游戏顺序就被破坏了 。我们现在陷入两难的境地，如何破解？

抓耳挠腮，撞破脑袋，终于想出一个迂回的解决思路：cards 当前的总分是固定、已知的，如果 g() 返回给我后手的后续最大得分，那当前总分减去该返回值，不就能够得到先手的后续得分了嘛！

漂亮！于是容易得到以下代码：

//sumPoints为cards的总分
int f(deque<int> cards, int sumPoints)
{
    if(cards.empty())
        return 0;
    int lpoint = cards.front();
    cards.pop_front();
    int a = sumPoints - g(cards, sumPoints - lpoint);
    cards.push_front(lpoint);
    int rpoint = cards.back();
    cards.pop_back();
    int b = sumPoints - g(cards, sumPoints - rpoint);
    return std::max(a, b);
}
int g(deque<int> cards, int sumPoints)
{
    if(cards.empty())
        return 0;
    int lpoint = cards.front();
    cards.pop_front();
    int a = sumPoints - f(cards, sumPoints - lpoint);
    cards.push_front(lpoint);
    int rpoint = cards.back();
    cards.pop_back();
    int b = sumPoints - f(cards, sumPoints - rpoint);
    return std::max(a, b);
}

到此问题已经被顺利解决了，接下来进行优化。

容易发现 f() 和 g() 完全对称，这说明二者可以合并为一个函数 ：

int getMaxPoints(deque<int> cards, int sumPoints)
{
    if(cards.empty())
        return 0;
    int lpoint = cards.front();
    cards.pop_front();
    int a = sumPoints - getMaxPoints(cards, sumPoints - lpoint);
    cards.push_front(lpoint);
    int rpoint = cards.back();
    cards.pop_back();
    int b = sumPoints - getMaxPoints(cards, sumPoints - rpoint);
    return std::max(a, b);
}

到此暴力递归版本顺利完成。

暴力递归-优化

从之前的题目练习中我们已经知道，如果要改为动态规划，那必须设计出良好的参数，即，状态变量最好为整形 。而上面的递归函数的状态变量却是 cards 和 sumPoints ，显然 cards 作为双端队列不利于进行动态规划。不慌，这很好改，再引入两个参数限制住范围即可：

int getMaxPoints(const vector<int>& cards, int left, int right, int sumPoints)
{
    if(left > right)
        return 0;
    int a = sumPoints - getMaxPoints(cards, left + 1, right, sumPoints - cards[left]);
    int b = sumPoints - getMaxPoints(cards, left , right - 1, sumPoints - cards[right]);
    return std::max(a, b);
}

每次取卡片时都只能在 left 或 right 处取得，同样能达到和之前一样的效果 。不禁赞叹，这代码简直简洁得不可思议！

这样我们就有了三个整形状态变量，完全可以放心地进行动态规划打表了。但分析后发现，sumPoints 不一定要作为参数传进来，因为在函数内部可以手动计算出 cards 的总分；且三维打表比二维打表更繁琐，稍不注意就会出错；另外，sumPoints 的值可能很大，造成较高的空间复杂度。综合而言，我们删去 sumPoints 参数，得到最终的递归版本：

int getMaxPoints(const vector<int>& cards, int left, int right)
{
    if(left > right)
        return 0;
    int sumPoints = 0;
    for(int i = left; i <= right; i++)
        sumPoints += cards[i];
    int a = sumPoints - getMaxPoints(cards, left + 1, right);
    int b = sumPoints - getMaxPoints(cards, left , right - 1);
    return std::max(a, b);
}

动态规划

二维打表，且位置依赖关系十分简单，直接给出代码：

int cardGame(const vector<int>& cards)
{
    vector<vector<int>> dp(cards.size(), vector<int>(cards.size(), 0));
    int size = cards.size();
    //求sumPoints优化:用sumTable记录范围和
    //sumTable[l][r]即为cards在[l,r]范围上的分数和
    vector<vector<int>> sumTable(size, vector<int>(size, 0));
    sumTable[0][0] = cards[0];
    for(int n = 1; n < size; n++)
    {//先求出[0,1],[0,2],[0,3],....,[0,n]范围上的分数和
        sumTable[0][n] = sumTable[0][n-1] + cards[n];
    }
    //再求出[r,l]范围上的分数和
    for(int l = 1; l < size; l++)
    {
        for(int r = l; r < size; r++)
        {
            sumTable[l][r] = sumTable[0][r] - sumTable[0][l-1];
        }
    }
    //按依赖打表
    for(int l = size - 1; l >= 0; l--)
    {
        for(int r = 0; r < size; r++)
        {
            //注意基线条件判断
            dp[l][r] = std::max(sumTable[l][r] - (l+1 > r ? 0 : dp[l+1][r]), sumTable[l][r] - (l > r-1 ? 0 : dp[l][r-1]));
        }
    }

    return std::max(dp[0][size-1], sumTable[0][size-1] - dp[0][size-1]);
}

对部分代码稍作解释：

• 在前面的暴力递归时，每一层递归中都必须循环计算出 sumPoints 的值。而在动态规划中，并不需要每次都重复计算，可以利用 sumTable 进行优化。先提前将 sumTable 建好，后续（第 27 行）要计算 cards 在 [r,l] 上的总分数时，直接取 sumTable[r][l] 即可，原理参看代码注释，不难懂。
• 第 27 行中别忘了判断基线条件。

总结

• 本题中玩家只有两个选择：从队首取或从队尾取，这与我们之前总结的“要或不要”模型本质是一致的，都是01问题。
• 这个思路中最漂亮的是对问题的转换：既然在 f() 中无法直接通过调用 f() 来取得先手的后续分数，那就迂回地通过 cards 总分减去后手的后续分数，进而取得先手的后续分数，妙。
• 类似的博弈问题还有石子游戏 ，区别是：本题不存在后手或先手一定赢，而石子游戏则是先手必定赢。