石子游戏Ⅲ

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" *，Bob 赢了就返回 "Bob"，*分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

提示：

• 1 <= stoneValue.length <= 5 * 104
• -1000 <= stoneValue[i] <= 1000

一维数组-动态规划-零和博弈-从结尾开始：

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> dp(n + 1, 0);

        for (int i = n - 1; i >= 0; i--)
        {
            dp[i] = INT_MIN;
            int sum = 0;
            for (int k = 0; k <= 2 && i + k < n; k++)
            {
                sum += stoneValue[i + k];
                dp[i] = max(dp[i], sum - dp[i + k + 1]);
            }
        }
        int res = dp[0];
        if (res > 0)
            return "Alice";
        else if (res < 0)
            return "Bob";
        else
            return "Tie";
    }
};

首先这个和预测赢家那题差不多，核心思想都是不去计算某个玩家具体能获得多少”分数“，而是求最大的”分差“，没看过的可以先去看看预测赢家的文章。

然后就是区别所在。首先，这道题目每个玩家都只能从前往后取，所以最后结束时取到的石子堆一定是排在最后的。而预测赢家由于可以从前取或者从后取，所以最后一个取的数字位置实际上是不知道的，这就造成了递推公式的不同。这里不讨论预测赢家的问题，专注于石子游戏。

假设一共有4堆石子，而我们现在想知道取几堆石子才是最优解。首先假设取 1 堆和 2 堆的情况。我们想要比较这两种情况哪个更好时，我们必须分别知道石子最后 3 堆和最后 2 堆时的最优解。

同理假设一共有7堆石子，而我们现在想知道取几堆石子才是最优解。同样假设取 1 堆和 2 堆的情况。我们想要比较这两种情况哪个更好时，我们必须分别知道石子最后 6 堆和最后 5 堆时的最优解。

所以我们在递推时，要从石子只剩最后 1 堆（所给数组的最后位置）开始，一直递推到题目开始的 n 堆。即给出 1，2，3，4，5，6时，我们从6开始，逐步推到5，6，再到4，5，6。

然后要解决的就是一次究竟取几堆石子才能取到最优解的问题。这里和预测赢家也差不多，都是列举各种情况，取最大值即可。