1406. 石子游戏 III

题目描述

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 * 10⁴
-1000 <= stoneValue[i] <= 1000

解法

方法一：记忆化搜索

思考

双方每次取 \(1\)～\(3\) 堆，若直接递归所有取法，状态树随 \(n\le 5\times 10^4\) 迅速膨胀，同一后缀会被反复计算。

对当前玩家而言，只需最大化「本轮取走石子之和减去对手在剩余局面上的最优差值」。定义 \(dfs(i)\) 为从下标 \(i\) 起的最优得分差，枚举取到 \(i,i+1,i+2\) 即可。

对 \(dfs(i)\) 记忆化后每个起点只计算一次。\(dfs(0)\) 的正负决定 Alice、Bob 或平局。

我们设计一个函数 \(dfs(i)\)，表示当前玩家在 \([i, n)\) 范围内进行游戏时，可以获得的最大得分差值。如果 \(dfs(0) \gt 0\)，则表示先手玩家 Alice 可以获胜；如果 \(dfs(0) \lt 0\)，则表示后手玩家 Bob 可以获胜；否则，表示两人打成平局。

函数 \(dfs(i)\) 的执行逻辑如下：

如果 \(i \geq n\)，说明当前没有石子可以拿了，直接返回 \(0\) 即可；
否则，我们枚举当前玩家拿走的最后一堆石子的下标 \(j\)，其中 \(i \le j \lt \min(i + 3, n)\)，即当前玩家拿走下标范围 \([i, j]\) 内的所有石子，得分之和为 \(\sum_{k=i}^{j} \textit{stoneValue}[k]\)，而另一个玩家在下一轮可以获得的得分差值为 \(dfs(j + 1)\)，从而当前玩家可以获得的得分差值为 \(\sum_{k=i}^{j} \textit{stoneValue}[k] - dfs(j + 1)\)。我们要使得当前玩家的得分差值最大，因此可以用 \(\max\) 函数得到最大得分差值，即：

\[ dfs(i) = \max_{i \le j < \min(i+3, n)} \left\{\sum_{k=i}^{j} \textit{stoneValue}[k] - dfs(j + 1)\right\} \]

为了防止重复计算，我们可以使用记忆化搜索。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是石子的堆数。

Python3JavaC++GoTypeScriptRust

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @cache
        def dfs(i: int) -> int:
            if i >= len(stoneValue):
                return 0
            ans = -inf
            s = 0
            for j in range(i, i + 3):
                if j >= len(stoneValue):
                    break
                s += stoneValue[j]
                ans = max(ans, s - dfs(j + 1))
            return ans

        res = dfs(0)
        if res == 0:
            return 'Tie'
        return 'Alice' if res > 0 else 'Bob'

class Solution {
    private int[] stoneValue;
    private Integer[] f;
    private int n;

    public String stoneGameIII(int[] stoneValue) {
        this.stoneValue = stoneValue;
        this.n = stoneValue.length;
        this.f = new Integer[n];

        int res = dfs(0);

        if (res == 0) {
            return "Tie";
        }
        return res > 0 ? "Alice" : "Bob";
    }

    private int dfs(int i) {
        if (i >= n) {
            return 0;
        }

        if (f[i] != null) {
            return f[i];
        }

        int ans = Integer.MIN_VALUE;
        int s = 0;

        for (int j = i; j < i + 3 && j < n; j++) {
            s += stoneValue[j];
            ans = Math.max(ans, s - dfs(j + 1));
        }

        return f[i] = ans;
    }
}

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

        auto dfs = [&](auto&& dfs, int i) -> int {
            if (i >= n) {
                return 0;
            }

            if (f[i] != INT_MIN) {
                return f[i];
            }

            int ans = INT_MIN;
            int s = 0;

            for (int j = i; j < i + 3 && j < n; j++) {
                s += stoneValue[j];
                ans = max(ans, s - dfs(dfs, j + 1));
            }

            return f[i] = ans;
        };

        int res = dfs(dfs, 0);

        if (res == 0) {
            return "Tie";
        }
        return res > 0 ? "Alice" : "Bob";
    }
};

func stoneGameIII(stoneValue []int) string {
    n := len(stoneValue)
    f := make([]int, n)

    for i := range f {
        f[i] = -1 << 30
    }

    var dfs func(int) int
    dfs = func(i int) int {
        if i >= n {
            return 0
        }

        if f[i] != -1<<30 {
            return f[i]
        }

        ans := -1 << 30
        s := 0

        for j := i; j < i+3 && j < n; j++ {
            s += stoneValue[j]
            ans = max(ans, s-dfs(j+1))
        }

        f[i] = ans
        return ans
    }

    res := dfs(0)

    if res == 0 {
        return "Tie"
    }
    if res > 0 {
        return "Alice"
    }
    return "Bob"
}

function stoneGameIII(stoneValue: number[]): string {
    const n = stoneValue.length;
    const f = new Array<number>(n).fill(Number.MIN_SAFE_INTEGER);

    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }

        if (f[i] !== Number.MIN_SAFE_INTEGER) {
            return f[i];
        }

        let ans = Number.MIN_SAFE_INTEGER;
        let s = 0;

        for (let j = i; j < i + 3 && j < n; j++) {
            s += stoneValue[j];
            ans = Math.max(ans, s - dfs(j + 1));
        }

        f[i] = ans;
        return ans;
    };

    const res = dfs(0);

    if (res === 0) {
        return 'Tie';
    }
    return res > 0 ? 'Alice' : 'Bob';
}

impl Solution {
    pub fn stone_game_iii(stone_value: Vec<i32>) -> String {
        let n = stone_value.len();
        let mut f = vec![None; n];

        fn dfs(i: usize, stone_value: &Vec<i32>, f: &mut Vec<Option<i32>>) -> i32 {
            if i >= stone_value.len() {
                return 0;
            }

            if let Some(v) = f[i] {
                return v;
            }

            let mut ans = i32::MIN;
            let mut s = 0;

            for j in i..(i + 3).min(stone_value.len()) {
                s += stone_value[j];
                ans = ans.max(s - dfs(j + 1, stone_value, f));
            }

            f[i] = Some(ans);
            ans
        }

        let res = dfs(0, &stone_value, &mut f);

        if res == 0 {
            "Tie".to_string()
        } else if res > 0 {
            "Alice".to_string()
        } else {
            "Bob".to_string()
        }
    }
}

1406. 石子游戏 III

题目描述

解法

方法一：记忆化搜索

评论