题目描述

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

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

状态表示：
集合-f[i]表示只考虑s[i]~s[n - 1]区间内的石头，所有博弈方案的集合
属性-先手者净胜分数的最大值

状态转移：
当一方位于i位置，有三种选择：
1.选择1堆，即赢得$s[i]$分，而你的对手将赢得$f[i + 1]$的分数，故净胜分为$s[i] - f[i + 1]$;
2.选择2堆，即赢得$s[i] + s[i + 1]$分，而你的对手将赢得$f[i + 2]$的分数，故净胜分为$s[i] + s[i + 1] - f[i + 2]$;
3.选择3堆，即赢得$s[i] + s[i + 1] + s[i + 2]$分，而你的对手将赢得$f[i + 3]$的分数，故净胜分为$s[i] + s[i + 1] + s[i + 2] - f[i + 3]$;
我们要求的属性是净胜分数的最大值，所以上述三种情况取max即可。

时间复杂度

遍历一次s数组，故时间复杂度为$O(n)$

空间复杂度

额外使用一个数组来存储状态，故为$O(n)$

参考文献

学习了wzc1995大神的题解。
https://www.acwing.com/solution/LeetCode/content/11028/

C++ 代码

class Solution {
public:
    string stoneGameIII(vector<int>& s) {
        int n = s.size();
        int f[n + 1]; memset(f, 0, sizeof f);

        for (int i = n - 1; i >= 0; --i){
            f[i] = s[i] - f[i + 1];
            if (i + 1 < n) f[i] = max(f[i], s[i] + s[i + 1] - f[i + 2]);
            if (i + 2 < n) f[i] = max(f[i], s[i] + s[i + 1] + s[i + 2] - f[i + 3]);
            // cout << i << ": " << f[i] << endl;
        }

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

算法2

(动态规划 空间优化版) $O(n)$

算法同算法1，只是将空间优化为$O(1)$。

时间复杂度

遍历一次s数组，故时间复杂度为$O(n)$

空间复杂度

额外使用了4个变量来存储状态，故为$O(1)$

参考文献

C++ 代码

class Solution {
public:
    string stoneGameIII(vector<int>& s) {
        int n = s.size();
        int f[n + 1]; memset(f, 0, sizeof f);
        int f0 = 0, f1 = 0, f2 = 0, f3 = 0;
        for (int i = n - 1; i >= 0; --i){
            f0 = s[i] - f1;
            if (i + 1 < n) f0 = max(f0, s[i] + s[i + 1] - f2);
            if (i + 2 < n) f0 = max(f0, s[i] + s[i + 1] + s[i + 2] - f3);
            // cout << i << ": " << f[i] << endl;
            f3 = f2; f2 = f1; f1 = f0;
        }

        if (f0 > 0) return "Alice";
        else if (f0 < 0) return "Bob";
        return "Tie";
    }
};