题目描述

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。

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

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略。如果 Alice 赢了就返回 "Alice"，Bob 赢了就返回 "Bob"，平局（分数相同）返回 "Tie"。

样例

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

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5。
之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。

如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3。
之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。

注意，他们都应该采取最优策略，所以在这里 Alice 将选择能够使她获胜的方案。

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

输入：values = [1,2,3,-1,-2,-3,7]
输出："Alice"

输入：values = [-1,-2,-3]
输出："Tie"

限制

• 1 <= values.length <= 50000
• -1000 <= values[i] <= 1000

算法

(动态规划) $O(n)$

1. 设状态 $f(i)$ 表示从第 $i$ 堆开始往后取，在最优策略下先手比后手能多赢的分数。假设下标从 0 开始到 n - 1。
2. 初始值，$f(n) = 0$，其余待定。
3. 转移时，对于 $f(i)$ 有三种决策，取第 $i$ 堆，取第 $i$ 和 $i + 1$ 堆，以及取第 $i$，$i + 1$ 和 $i + 2$ 堆，对应的转移分别为 $\max(s(i) - f(i + 1), s(i) + s(i + 1) - f(i + 2), s(i) + s(i + 1) + s(i + 2) - f(i + 3)$。
4. 最终，如果 $f(0) = 0$，则平局；如果 $f(0) > 0$ 则 Alice 胜，否则 Bob 胜。

时间复杂度

• 状态数为 $O(n)$，每次转移仅需要常数时间，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储数组，可以通过用若干变量替代状态将空间复杂度降到常数。

C++ 代码

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

        f[n] = 0;

        for (int i = n - 1; i >= 0; i--) {
            f[i] = stoneValue[i] - f[i + 1];
            if (i < n - 1)
                f[i] = max(f[i], stoneValue[i] + stoneValue[i + 1] - f[i + 2]);

            if (i < n - 2)
                f[i] = max(f[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] 
                                    - f[i + 3]);
        }

        if (f[0] == 0)
            return "Tie";
        else if (f[0] > 0)
            return "Alice";
        else return "Bob";
    }
};