LeetCode1140-石子游戏II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/stone-game-ii/

中文链接：https://leetcode-cn.com/problems/stone-game-ii/

题目详述

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

示例：

1
2
3
4
5
6
输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。

提示：

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

题目详解

minmax 问题。

  • 定义 dfs(s, M) 为两个玩家从 s 开始、给定值 M 的最大分数差值。
  • 进行记忆化搜索，那么 cache[s][M] = max{sum(piles[s:s+x]) - dfs(s + x, max(x, M))}, 1 <= x <= 2 * M, s + x <= n。
  • 最终先手与后手的最大相对差值为 dfs(0, 1)，加上所有分数之和除以二，就是先手得到的最大分数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class LeetCode_01140 {

    public int stoneGameII(int[] piles) {
        Map<Integer, Integer> map = new HashMap<>();
        int total = Arrays.stream(piles).sum();
        return (total + dfs(0, 1, piles, map)) >> 1;
    }

    private int dfs(int s, int M, int[] piles, Map<Integer, Integer> map) {
        if (s >= piles.length) {
            return 0;
        }
        // 两个参数化为一个参数作为 key
        int key = s << 8 | M;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        // 直接取完
        if (s + 2 * M >= piles.length) {
            int res = 0;
            for (int i = s; i < piles.length; ++i) {
                res += piles[i];
            }
            return res;
        }
        int best = Integer.MIN_VALUE;
        int cur = 0;
        for (int x = 1; x <= 2 * M && s + x - 1 < piles.length; ++x) {
            cur += piles[s + x - 1];
            best = Math.max(best, cur - dfs(s + x, Math.max(x, M), piles, map));
        }
        map.put(key, best);
        return best;
    }
}